From 0580ff3941fe5f5ea25c96e737edba1541d9271f Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Tue, 23 Jun 2015 14:54:00 +0200 Subject: [PATCH] box/box intersection test only boolean test for now --- src/model/geometry.cpp | 65 ++++++++++++++++++++++++++++++++++++++ src/model/geometry.hpp | 6 ++++ tst/model/GeometryTest.cpp | 36 ++++++++++++++++++++- tst/model/GeometryTest.hpp | 6 ++-- 4 files changed, 110 insertions(+), 3 deletions(-) diff --git a/src/model/geometry.cpp b/src/model/geometry.cpp index ed9b4b7..b08d59f 100644 --- a/src/model/geometry.cpp +++ b/src/model/geometry.cpp @@ -65,6 +65,71 @@ bool Intersection( return true; } + +bool Intersection( + const AABB &a_box, + const glm::mat4 &a_m, + const AABB &b_box, + const glm::mat4 &b_m +) noexcept { + glm::vec3 a_corners[8] = { + glm::vec3(a_m * glm::vec4(a_box.min.x, a_box.min.y, a_box.min.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.min.x, a_box.min.y, a_box.max.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.min.x, a_box.max.y, a_box.min.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.min.x, a_box.max.y, a_box.max.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.max.x, a_box.min.y, a_box.min.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.max.x, a_box.min.y, a_box.max.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.max.x, a_box.max.y, a_box.min.z, 1)), + glm::vec3(a_m * glm::vec4(a_box.max.x, a_box.max.y, a_box.max.z, 1)), + }; + + glm::vec3 b_corners[8] = { + glm::vec3(b_m * glm::vec4(b_box.min.x, b_box.min.y, b_box.min.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.min.x, b_box.min.y, b_box.max.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.min.x, b_box.max.y, b_box.min.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.min.x, b_box.max.y, b_box.max.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.max.x, b_box.min.y, b_box.min.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.max.x, b_box.min.y, b_box.max.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.max.x, b_box.max.y, b_box.min.z, 1)), + glm::vec3(b_m * glm::vec4(b_box.max.x, b_box.max.y, b_box.max.z, 1)), + }; + + glm::vec3 axes[6] = { + glm::vec3(a_m * glm::vec4(1, 0, 0, 0)), + glm::vec3(a_m * glm::vec4(0, 1, 0, 0)), + glm::vec3(a_m * glm::vec4(0, 0, 1, 0)), + glm::vec3(b_m * glm::vec4(1, 0, 0, 0)), + glm::vec3(b_m * glm::vec4(0, 1, 0, 0)), + glm::vec3(b_m * glm::vec4(0, 0, 1, 0)), + }; + + for (const glm::vec3 &axis : axes) { + float a_min = std::numeric_limits::infinity(); + float a_max = -std::numeric_limits::infinity(); + for (const glm::vec3 &corner : a_corners) { + float val = glm::dot(corner, axis); + a_min = std::min(a_min, val); + a_max = std::max(a_max, val); + } + + float b_min = std::numeric_limits::infinity(); + float b_max = -std::numeric_limits::infinity(); + for (const glm::vec3 &corner : b_corners) { + float val = glm::dot(corner, axis); + b_min = std::min(b_min, val); + b_max = std::max(b_max, val); + } + + if (a_max < b_min || b_max < a_min) return false; + } + + // TODO: find intersection point and normals + // normal could be deduced from the axis with the lowest min? + + return true; +} + + bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept { // transform corners into clip space glm::vec4 corners[8] = { diff --git a/src/model/geometry.hpp b/src/model/geometry.hpp index d6e3d28..f4498f5 100644 --- a/src/model/geometry.hpp +++ b/src/model/geometry.hpp @@ -36,6 +36,12 @@ bool Intersection( float *dist = nullptr, glm::vec3 *normal = nullptr) noexcept; +bool Intersection( + const AABB &a_box, + const glm::mat4 &a_m, + const AABB &b_box, + const glm::mat4 &b_m) noexcept; + bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept; } diff --git a/tst/model/GeometryTest.cpp b/tst/model/GeometryTest.cpp index 51985ae..71830c6 100644 --- a/tst/model/GeometryTest.cpp +++ b/tst/model/GeometryTest.cpp @@ -4,6 +4,7 @@ #include #include +#include CPPUNIT_TEST_SUITE_REGISTRATION(blank::test::GeometryTest); @@ -18,7 +19,7 @@ void GeometryTest::tearDown() { } -void GeometryTest::testRayAABBIntersection() { +void GeometryTest::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 glm::mat4 M(1); // no transformation @@ -62,5 +63,38 @@ void GeometryTest::testRayAABBIntersection() { ); } +void GeometryTest::testBoxBoxIntersection() { + AABB box{ { -1, -1, -1 }, { 1, 1, 1 } }; // 2x2x2 cube centered around origin + glm::mat4 Ma(1); // identity + glm::mat4 Mb(1); // identity + // they're identical, so should probably intersect ^^ + + CPPUNIT_ASSERT_MESSAGE( + "identical OBBs don't intersect", + Intersection(box, Ma, box, Mb) + ); + + Ma = glm::translate(glm::vec3(-2, 0, 0)); // 2 to the left + Mb = glm::translate(glm::vec3(2, 0, 0)); // 2 to the right + CPPUNIT_ASSERT_MESSAGE( + "distant OBBs intersect (2 apart, no rotation)", + !Intersection(box, Ma, box, Mb) + ); + + Ma = glm::rotate(PI_0p25, glm::vec3(0, 0, 1)); // rotated 45° around Z + Mb = glm::translate(glm::vec3(2.4, 0, 0)); // 2.4 to the right + // they should barely touch. intersect by about 0.01 if my head works + CPPUNIT_ASSERT_MESSAGE( + "OBBs don't intersect (one rotated by 45°)", + Intersection(box, Ma, box, Mb) + ); + + Mb = glm::translate(glm::vec3(3, 0, 0)); // 3 to the right + CPPUNIT_ASSERT_MESSAGE( + "OBBs intersect (one rotated by 45°)", + !Intersection(box, Ma, box, Mb) + ); +} + } } diff --git a/tst/model/GeometryTest.hpp b/tst/model/GeometryTest.hpp index 2ee85b1..7ba2d2d 100644 --- a/tst/model/GeometryTest.hpp +++ b/tst/model/GeometryTest.hpp @@ -12,7 +12,8 @@ class GeometryTest CPPUNIT_TEST_SUITE(GeometryTest); -CPPUNIT_TEST(testRayAABBIntersection); +CPPUNIT_TEST(testRayBoxIntersection); +CPPUNIT_TEST(testBoxBoxIntersection); CPPUNIT_TEST_SUITE_END(); @@ -20,7 +21,8 @@ public: void setUp(); void tearDown(); - void testRayAABBIntersection(); + void testRayBoxIntersection(); + void testBoxBoxIntersection(); }; -- 2.39.2