faster ray/box test for AABBs

diff --git a/src/geometry/geometry.cpp b/src/geometry/geometry.cpp
index 1e84fbb9068d1749fbe5a3edcc81519aa7718e87..668e72930c9bfbe91de362de09fc0f59660e9c95 100644 (file)
--- a/src/geometry/geometry.cpp
+++ b/src/geometry/geometry.cpp
@@ -49,6 +49,23 @@ 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,
@@ -85,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;
@@ -106,7 +122,6 @@ bool Intersection(
        return true;
 }
 
-
 bool Intersection(
        const AABB &a_box,
        const glm::mat4 &a_m,

diff --git a/src/geometry/primitive.hpp b/src/geometry/primitive.hpp
index da4c37f1e03296d254d55f051d5e199f94132a9c..72da84749140ca6f2d6b2c71a069c3fd9c031199 100644 (file)
--- a/src/geometry/primitive.hpp
+++ b/src/geometry/primitive.hpp
@@ -31,13 +31,29 @@ struct AABB {
 
 std::ostream &operator <<(std::ostream &, const AABB &);
 
+// TODO: this should really use setters/getters for dir and inv_dir so
+//       manipulating code doesn't "forget" to call Update()
 struct Ray {
        glm::vec3 orig;
        glm::vec3 dir;
+
+       glm::vec3 inv_dir;
+
+       void Update() noexcept {
+               inv_dir = 1.0f / dir;
+       }
 };
 
 std::ostream &operator <<(std::ostream &, const Ray &);
 
+/// axis aligned boolean ray/box intersection test
+/// if true, dist constains distance from ray's origin to intersection point
+bool Intersection(
+       const Ray &,
+       const AABB &,
+       float &dist) noexcept;
+
+/// detailed oriented ray/box intersection test
 bool Intersection(
        const Ray &,
        const AABB &,

diff --git a/src/world/Chunk.hpp b/src/world/Chunk.hpp
index 7eceb980cb62d6c66918ae9b3eb7fa587416c2c3..045f58df7d6ac29f1140fea27849cc212aea5e30 100644 (file)
--- a/src/world/Chunk.hpp
+++ b/src/world/Chunk.hpp
@@ -35,6 +35,14 @@ public:
        static glm::vec3 Center() noexcept { return glm::vec3(8.0f); }
        static float Radius() noexcept { return 27.71281292110203669632f; /* 16 * √3 */ }
 
+       /// get bounding box relative to given reference chunk
+       AABB RelativeBounds(const ExactLocation::Coarse &ref) const noexcept {
+               AABB bounds;
+               bounds.min = (position - ref) * ExactLocation::Extent();
+               bounds.max = bounds.min + ExactLocation::FExtent();
+               return bounds;
+       }
+
        static constexpr bool InBounds(const ExactLocation::Fine &pos) noexcept {
                return
                        pos.x >= 0.0f && pos.x < fside &&
@@ -141,7 +149,7 @@ public:
                const ExactLocation::Coarse &reference,
                float &dist
        ) const noexcept {
-               return blank::Intersection(ray, Bounds(), Transform(reference), &dist);
+               return blank::Intersection(ray, RelativeBounds(reference), dist);
        }
 
        /// check if given ray intersects any block of this chunk

diff --git a/src/world/world.cpp b/src/world/world.cpp
index bf68a9eca412f295c977e486c465e0794025366a..0daadfc430afe9e56e6be35a2aba9876d4dcd03d 100644 (file)
--- a/src/world/world.cpp
+++ b/src/world/world.cpp
@@ -133,7 +133,9 @@ glm::mat4 Entity::ViewTransform(const glm::ivec3 &reference) const noexcept {
 
 Ray Entity::Aim(const ExactLocation::Coarse &chunk_offset) const noexcept {
        glm::mat4 transform = ViewTransform(chunk_offset);
-       return Ray{ glm::vec3(transform[3]), -glm::vec3(transform[2]) };
+       Ray ray{ glm::vec3(transform[3]), -glm::vec3(transform[2]) };
+       ray.Update();
+       return ray;
 }
 
 void Entity::Update(World &world, float dt) {
@@ -789,8 +791,11 @@ bool World::Intersection(
 
        candidates.clear();
 
-       // TODO: convert to coords based iteration and trim based
-       //       on ray direction
+       // TODO: change this so the test starts at the chunk of the ray's
+       //       origin and "walks" forward until it hits (actually casting
+       //       the ray, so to say). if this performs well (at least, better
+       //       than now), this could also qualify for the chunk test itself
+       //       see Bresenham's line algo or something similar
        for (Chunk *cur_chunk : *index) {
                float cur_dist;
                if (cur_chunk && cur_chunk->Intersection(ray, reference, cur_dist)) {

diff --git a/tst/geometry/IntersectionTest.cpp b/tst/geometry/IntersectionTest.cpp
index 41fb81a8764b6c5b955f8bb9c13d8ef5b4253afa..521647e5115b9a3e23aeb168fa1fb81eb2dfb9ea 100644 (file)
--- a/tst/geometry/IntersectionTest.cpp
+++ b/tst/geometry/IntersectionTest.cpp
@@ -20,6 +20,53 @@ void IntersectionTest::tearDown() {
 }
 
 
+void IntersectionTest::testSimpleRayBoxIntersection() {
+       Ray ray{ { 0, 0, 0 }, { 1, 0, 0 } }; // at origin, pointing right
+       ray.Update();
+       AABB box{ { -1, -1, -1 }, { 1, 1, 1 } }; // 2x2x2 cube centered around origin
+
+       const float delta = std::numeric_limits<float>::epsilon();
+
+       float distance = 0;
+
+       CPPUNIT_ASSERT_MESSAGE(
+               "ray at origin not intersecting box at origin",
+               Intersection(ray, box, distance)
+       );
+
+       // move ray outside the box, but have it still point at it
+       // should be 4 units to the left now
+       ray.orig.x = -5;
+       CPPUNIT_ASSERT_MESSAGE(
+               "ray pointing at box doesn't intersect",
+               Intersection(ray, box, distance)
+       );
+       CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE(
+               "intersection distance way off",
+               4.0f, distance, delta
+       );
+
+       // move ray to the other side, so it's pointing away now
+       ray.orig.x = 5;
+       CPPUNIT_ASSERT_MESSAGE(
+               "ray pointing away from box still intersects",
+               !Intersection(ray, box, distance)
+       );
+
+       // 45 deg down from 4 units away, so should be about 4 * sqrt(2)
+       ray.orig = { -5.0f, 4.5f, 0.0f };
+       ray.dir = { 0.70710678118654752440f, -0.70710678118654752440f, 0.0f };
+       ray.Update();
+       CPPUNIT_ASSERT_MESSAGE(
+               "ray pointing at box doesn't intersect",
+               Intersection(ray, box, distance)
+       );
+       CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE(
+               "intersection distance way off",
+               5.65685424949238019520f, distance, delta
+       );
+}
+
 void IntersectionTest::testRayBoxIntersection() {
        Ray ray{ { 0, 0, 0 }, { 1, 0, 0 } }; // at origin, pointing right
        AABB box{ { -1, -1, -1 }, { 1, 1, 1 } }; // 2x2x2 cube centered around origin
@@ -34,10 +81,6 @@ void IntersectionTest::testRayBoxIntersection() {
                "ray at origin not intersecting box at origin",
                Intersection(ray, box, M, &distance)
        );
-       CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE(
-               "intersection distance way off",
-               0.0f, distance, delta
-       );
        // normal undefined, so can't test
 
        // move ray outside the box, but have it still point at it
@@ -62,6 +105,22 @@ void IntersectionTest::testRayBoxIntersection() {
                "ray pointing away from box still intersects",
                !Intersection(ray, box, M)
        );
+
+       // 45 deg down from 4 units away, so should be about 4 * sqrt(2)
+       ray.orig = { -5.0f, 4.5f, 0.0f };
+       ray.dir = { 0.70710678118654752440f, -0.70710678118654752440f, 0.0f };
+       CPPUNIT_ASSERT_MESSAGE(
+               "ray pointing at box doesn't intersect",
+               Intersection(ray, box, M, &distance, &normal)
+       );
+       CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE(
+               "intersection distance way off",
+               5.65685424949238019520f, distance, delta
+       );
+       CPPUNIT_ASSERT_EQUAL_MESSAGE(
+               "wrong surface normal at intersection point",
+               glm::vec3(-1, 0, 0), normal
+       );
 }
 
 void IntersectionTest::testBoxBoxIntersection() {

diff --git a/tst/geometry/IntersectionTest.hpp b/tst/geometry/IntersectionTest.hpp
index 7922290da8f5bc59c6064c9fc858b30c59dd2f26..6300e6e4d8cdb2c435fd244d283cf69406a35215 100644 (file)
--- a/tst/geometry/IntersectionTest.hpp
+++ b/tst/geometry/IntersectionTest.hpp
@@ -12,6 +12,7 @@ class IntersectionTest
 
 CPPUNIT_TEST_SUITE(IntersectionTest);
 
+CPPUNIT_TEST(testSimpleRayBoxIntersection);
 CPPUNIT_TEST(testRayBoxIntersection);
 CPPUNIT_TEST(testBoxBoxIntersection);
 
@@ -21,6 +22,7 @@ public:
        void setUp();
        void tearDown();
 
+       void testSimpleRayBoxIntersection();
        void testRayBoxIntersection();
        void testBoxBoxIntersection();