faster chunk culling test

also seems to cull some more, need to check if it
doesn't accidentally cull a little too much

diff --git a/src/geometry/geometry.cpp b/src/geometry/geometry.cpp
index 7798d33e949362ede44727f75402832e87a286ae..1e84fbb9068d1749fbe5a3edcc81519aa7718e87 100644 (file)
--- a/src/geometry/geometry.cpp
+++ b/src/geometry/geometry.cpp
@@ -4,6 +4,8 @@
 #include "rotation.hpp"
 
 #include <limits>
+#include <ostream>
+#include <glm/gtx/io.hpp>
 #include <glm/gtx/matrix_cross_product.hpp>
 #include <glm/gtx/optimum_pow.hpp>
 #include <glm/gtx/transform.hpp>
@@ -39,6 +41,14 @@ glm::mat3 find_rotation(const glm::vec3 &a, const glm::vec3 &b) noexcept {
        return glm::mat3(1.0f) + vx + (pow2(vx) * f);
 }
 
+std::ostream &operator <<(std::ostream &out, const AABB &box) {
+       return out << "AABB(" << box.min << ", " << box.max << ')';
+}
+
+std::ostream &operator <<(std::ostream &out, const Ray &ray) {
+       return out << "Ray(" << ray.orig << ", " << ray.dir << ')';
+}
+
 bool Intersection(
        const Ray &ray,
        const AABB &aabb,
@@ -187,6 +197,21 @@ bool Intersection(
 }
 
 
+std::ostream &operator <<(std::ostream &out, const Plane &plane) {
+       return out << "Plane(" << plane.normal << ", " << plane.dist << ')';
+}
+
+std::ostream &operator <<(std::ostream &out, const Frustum &frustum) {
+       return out << "Frustum(" << std::endl
+               << "\tleft:   " << frustum.plane[0] << std::endl
+               << "\tright:  " << frustum.plane[1] << std::endl
+               << "\tbottom: " << frustum.plane[2] << std::endl
+               << "\ttop:    " << frustum.plane[3] << std::endl
+               << "\tnear:   " << frustum.plane[4] << std::endl
+               << "\tfar:    " << frustum.plane[5] << std::endl
+               << ')';
+}
+
 bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept {
        // transform corners into clip space
        glm::vec4 corners[8] = {
@@ -223,4 +248,18 @@ bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept {
        return false;
 }
 
+bool CullTest(const AABB &box, const Frustum &frustum) noexcept {
+       for (const Plane &plane : frustum.plane) {
+               const glm::vec3 np(
+                       ((plane.normal.x > 0.0f) ? box.max.x : box.min.x),
+                       ((plane.normal.y > 0.0f) ? box.max.y : box.min.y),
+                       ((plane.normal.z > 0.0f) ? box.max.z : box.min.z)
+               );
+               const float dp = dot(plane.normal, np);
+               // cull if nearest point is on the "outside" side of the plane
+               if (dp < -plane.dist) return true;
+       }
+       return false;
+}
+
 }

diff --git a/src/geometry/primitive.hpp b/src/geometry/primitive.hpp
index cdeae86e5c68b21303b7c27c775d9ff657df8924..da4c37f1e03296d254d55f051d5e199f94132a9c 100644 (file)
--- a/src/geometry/primitive.hpp
+++ b/src/geometry/primitive.hpp
@@ -2,6 +2,7 @@
 #define BLANK_GEOMETRY_PRIMITIVE_HPP_
 
 #include <algorithm>
+#include <iosfwd>
 #include <glm/glm.hpp>
 
 
@@ -28,11 +29,15 @@ struct AABB {
        }
 };
 
+std::ostream &operator <<(std::ostream &, const AABB &);
+
 struct Ray {
        glm::vec3 orig;
        glm::vec3 dir;
 };
 
+std::ostream &operator <<(std::ostream &, const Ray &);
+
 bool Intersection(
        const Ray &,
        const AABB &,
@@ -50,7 +55,72 @@ bool Intersection(
        float &depth,
        glm::vec3 &normal) noexcept;
 
-bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept;
+
+struct Plane {
+       glm::vec3 normal;
+       float dist;
+
+       float &A() noexcept { return normal.x; }
+       float &B() noexcept { return normal.y; }
+       float &C() noexcept { return normal.z; }
+       float &D() noexcept { return dist; }
+       float A() const noexcept { return normal.x; }
+       float B() const noexcept { return normal.y; }
+       float C() const noexcept { return normal.z; }
+       float D() const noexcept { return dist; }
+
+       Plane(const glm::vec3 &n, float d)
+       : normal(n), dist(d) { }
+       Plane(const glm::vec4 &abcd)
+       : normal(abcd), dist(abcd.w) { }
+
+       void Normalize() noexcept {
+               const float l = length(normal);
+               normal /= l;
+               dist /= l;
+       }
+};
+
+std::ostream &operator <<(std::ostream &, const Plane &);
+
+struct Frustum {
+       Plane plane[6];
+       Plane &Left() noexcept { return plane[0]; }
+       Plane &Right() noexcept { return plane[1]; }
+       Plane &Bottom() noexcept { return plane[2]; }
+       Plane &Top() noexcept { return plane[3]; }
+       Plane &Near() noexcept { return plane[4]; }
+       Plane &Far() noexcept { return plane[5]; }
+       const Plane &Left() const noexcept { return plane[0]; }
+       const Plane &Right() const noexcept { return plane[1]; }
+       const Plane &Bottom() const noexcept { return plane[2]; }
+       const Plane &Top() const noexcept { return plane[3]; }
+       const Plane &Near() const noexcept { return plane[4]; }
+       const Plane &Far() const noexcept { return plane[5]; }
+
+       /// create frustum from transposed MVP
+       Frustum(const glm::mat4 &mat)
+       : plane{
+               { mat[3] + mat[0] },
+               { mat[3] - mat[0] },
+               { mat[3] + mat[1] },
+               { mat[3] - mat[1] },
+               { mat[3] + mat[2] },
+               { mat[3] - mat[2] },
+       } { }
+
+       void Normalize() noexcept {
+               for (Plane &p : plane) {
+                       p.Normalize();
+               }
+       }
+};
+
+std::ostream &operator <<(std::ostream &, const Plane &);
+std::ostream &operator <<(std::ostream &, const Frustum &);
+
+bool CullTest(const AABB &box, const glm::mat4 &) noexcept;
+bool CullTest(const AABB &box, const Frustum &) noexcept;
 
 }
 

diff --git a/src/world/chunk.cpp b/src/world/chunk.cpp
index d124eb7373c8b4d34ab65406f4db4bb0cf350ffe..6eb027a58f233173dc1026de7da64e4931ad7f59 100644 (file)
--- a/src/world/chunk.cpp
+++ b/src/world/chunk.cpp
@@ -19,6 +19,9 @@
 #include <ostream>
 #include <queue>
 
+#include <iostream>
+#include <glm/gtx/io.hpp>
+
 
 namespace blank {
 
@@ -809,19 +812,36 @@ void ChunkRenderer::Render(Viewport &viewport) {
        chunk_prog.SetTexture(block_tex);
        chunk_prog.SetFogDensity(fog_density);
 
+       Frustum frustum(transpose(chunk_prog.GetVP()));
+       AABB box;
+
+       //std::cout << "V = " << chunk_prog.View() << std::endl;
+       //std::cout << "P = " << chunk_prog.Projection() << std::endl;
+       //std::cout << "VP = " << chunk_prog.GetVP() << std::endl;
+       //std::cout << "frustum = " << frustum << std::endl;
+
        for (int i = 0; i < index.TotalChunks(); ++i) {
                if (!index[i]) continue;
-               // TODO: optimize chunk culling, shoudn't be that hard
-               glm::mat4 m(index[i]->Transform(index.Base()));
-               glm::mat4 mvp(chunk_prog.GetVP() * m);
-               if (!CullTest(Chunk::Bounds(), mvp)) {
+               box.min = (index[i]->Position() - index.Base()) * ExactLocation::Extent();
+               box.max = box.min + ExactLocation::FExtent();
+
+               if (!CullTest(box, frustum)) {
+
+                       //glm::mat4 m(index[i]->Transform(index.Base()));
+                       //if (CullTest(Chunk::Bounds(), chunk_prog.GetVP() * m)) {
+                       //      std::cout << "M = " << m << std::endl;
+                       //      std::cout << "box = " << box.min << ", " << box.max << std::endl;
+                       //      std::cout << "should've been culled" << std::endl;
+                       //}
+
                        if (index[i]->ShouldUpdateMesh()) {
                                index[i]->Update(models[i]);
                        }
-                       chunk_prog.SetM(m);
+                       chunk_prog.SetM(index[i]->Transform(index.Base()));
                        models[i].Draw();
                }
        }
+       //std::cout << std::endl;
 }