faster ray/box test for AABBs

[blank.git] / src / geometry / geometry.cpp

diff --git a/src/geometry/geometry.cpp b/src/geometry/geometry.cpp
index ebd47e9ab9cb10aebe5a7ec760ee74d368dfb460..668e72930c9bfbe91de362de09fc0f59660e9c95 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,31 @@ 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 &box,
+       float &dist
+) noexcept {
+       float t_min = 0.0f;
+       float t_max = std::numeric_limits<float>::infinity();
+       for (int i = 0; i < 3; ++i) {
+               float t1 = (box.min[i] - ray.orig[i]) * ray.inv_dir[i];
+               float t2 = (box.max[i] - ray.orig[i]) * ray.inv_dir[i];
+               t_min = std::max(t_min, std::min(t1, t2));
+               t_max = std::min(t_max, std::max(t1, t2));
+       }
+       dist = t_min;
+       return t_max >= t_min;
+}
+
 bool Intersection(
        const Ray &ray,
        const AABB &aabb,
@@ -75,12 +102,11 @@ bool Intersection(
                }
        }
 
-       glm::vec3 min_all(min(t1, t2));
-
        if (dist) {
                *dist = t_min;
        }
        if (normal) {
+               glm::vec3 min_all(min(t1, t2));
                if (min_all.x > min_all.y) {
                        if (min_all.x > min_all.z) {
                                normal->x = t2.x < t1.x ? 1 : -1;
@@ -96,7 +122,6 @@ bool Intersection(
        return true;
 }
 
-
 bool Intersection(
        const AABB &a_box,
        const glm::mat4 &a_m,
@@ -187,6 +212,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] = {
@@ -199,21 +239,19 @@ bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept {
                { box.max.x, box.max.y, box.min.z, 1.0f },
                { box.max.x, box.max.y, box.max.z, 1.0f },
        };
+
+       // check how many corners lie outside
+       int hits[6] = { 0, 0, 0, 0, 0, 0 };
        for (glm::vec4 &corner : corners) {
                corner = MVP * corner;
+               // replacing this with *= 1/w is effectively more expensive
                corner /= corner.w;
-       }
-
-       int hits[6] = { 0, 0, 0, 0, 0, 0 };
-
-       // check how many corners lie outside
-       for (const glm::vec4 &corner : corners) {
-               if (corner.x >  1.0f) ++hits[0];
-               if (corner.x < -1.0f) ++hits[1];
-               if (corner.y >  1.0f) ++hits[2];
-               if (corner.y < -1.0f) ++hits[3];
-               if (corner.z >  1.0f) ++hits[4];
-               if (corner.z < -1.0f) ++hits[5];
+               hits[0] += (corner.x >  1.0f);
+               hits[1] += (corner.x < -1.0f);
+               hits[2] += (corner.y >  1.0f);
+               hits[3] += (corner.y < -1.0f);
+               hits[4] += (corner.z >  1.0f);
+               hits[5] += (corner.z < -1.0f);
        }
 
        // if all corners are outside any given clip plane, the test is true
@@ -225,4 +263,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;
+}
+
 }