From: Daniel Karbach Date: Mon, 21 Dec 2015 12:14:44 +0000 (+0100) Subject: faster ray/box test for AABBs X-Git-Url: http://git.localhorst.tv/?p=blank.git;a=commitdiff_plain;h=ab0ba4313c473378b4516e3702d524dc1d1fc5d4 faster ray/box test for AABBs --- diff --git a/src/geometry/geometry.cpp b/src/geometry/geometry.cpp index 1e84fbb..668e729 100644 --- 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::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 da4c37f..72da847 100644 --- 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 7eceb98..045f58d 100644 --- 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 bf68a9e..0daadfc 100644 --- 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 41fb81a..521647e 100644 --- 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::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 7922290..6300e6e 100644 --- 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();