From 419e33e565bffbaf0416ed4a5f80e9c81f62a479 Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Thu, 25 Jun 2015 15:26:58 +0200 Subject: [PATCH] figure out depth and normal in box/box test --- src/model/geometry.cpp | 20 ++++++++++++++++---- src/model/geometry.hpp | 8 +++++++- src/model/shape.cpp | 8 ++++++-- src/world/World.cpp | 2 ++ src/world/chunk.cpp | 6 +++++- tst/model/GeometryTest.cpp | 29 ++++++++++++++++++++++++----- 6 files changed, 60 insertions(+), 13 deletions(-) diff --git a/src/model/geometry.cpp b/src/model/geometry.cpp index b08d59f..c2816b4 100644 --- a/src/model/geometry.cpp +++ b/src/model/geometry.cpp @@ -70,7 +70,9 @@ bool Intersection( const AABB &a_box, const glm::mat4 &a_m, const AABB &b_box, - const glm::mat4 &b_m + const glm::mat4 &b_m, + float &depth, + glm::vec3 &normal ) 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)), @@ -103,6 +105,10 @@ bool Intersection( glm::vec3(b_m * glm::vec4(0, 0, 1, 0)), }; + depth = std::numeric_limits::infinity(); + int min_axis = 0; + + int cur_axis = 0; for (const glm::vec3 &axis : axes) { float a_min = std::numeric_limits::infinity(); float a_max = -std::numeric_limits::infinity(); @@ -121,11 +127,17 @@ bool Intersection( } 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? + float overlap = std::min(a_max, b_max) - std::max(a_min, b_min); + if (overlap < depth) { + depth = overlap; + min_axis = cur_axis; + } + + ++cur_axis; + } + normal = axes[min_axis]; return true; } diff --git a/src/model/geometry.hpp b/src/model/geometry.hpp index f4498f5..df45fff 100644 --- a/src/model/geometry.hpp +++ b/src/model/geometry.hpp @@ -22,6 +22,10 @@ struct AABB { if (max.y < min.y) std::swap(max.y, min.y); if (max.z < min.z) std::swap(max.z, min.z); } + + glm::vec3 Center() const noexcept { + return min + (max - min) * 0.5f; + } }; struct Ray { @@ -40,7 +44,9 @@ bool Intersection( const AABB &a_box, const glm::mat4 &a_m, const AABB &b_box, - const glm::mat4 &b_m) noexcept; + const glm::mat4 &b_m, + float &depth, + glm::vec3 &normal) noexcept; bool CullTest(const AABB &box, const glm::mat4 &MVP) noexcept; diff --git a/src/model/shape.cpp b/src/model/shape.cpp index 8265943..8aa1c25 100644 --- a/src/model/shape.cpp +++ b/src/model/shape.cpp @@ -180,7 +180,9 @@ bool CuboidShape::Intersects( const AABB &box, const glm::mat4 &box_M ) const noexcept { - return Intersection(bb, M, box, box_M); + float depth; + glm::vec3 normal; + return Intersection(bb, M, box, box_M, depth, normal); } @@ -347,7 +349,9 @@ bool StairShape::Intersects( const AABB &box, const glm::mat4 &box_M ) const noexcept { - return Intersection(bot, M, box, box_M) || Intersection(top, M, box, box_M); + float depth; + glm::vec3 normal; + return Intersection(bot, M, box, box_M, depth, normal) || Intersection(top, M, box, box_M, depth, normal); } } diff --git a/src/world/World.cpp b/src/world/World.cpp index 82701ce..4ab116c 100644 --- a/src/world/World.cpp +++ b/src/world/World.cpp @@ -178,6 +178,8 @@ bool World::Intersection( bool World::Intersection(const Entity &e) { AABB box = e.Bounds(); glm::mat4 M = e.Transform(player->ChunkCoords()); + // TODO: this only needs to check the chunks surrounding the entity's chunk position + // need find out if that is quicker than the rough chunk bounds test for (Chunk &cur_chunk : chunks.Loaded()) { if (cur_chunk.Intersection(box, M, cur_chunk.Transform(player->ChunkCoords()))) { return true; diff --git a/src/world/chunk.cpp b/src/world/chunk.cpp index 2216617..7591266 100644 --- a/src/world/chunk.cpp +++ b/src/world/chunk.cpp @@ -5,6 +5,7 @@ #include "Generator.hpp" #include +#include #include #include @@ -486,7 +487,10 @@ bool Chunk::Intersection( const glm::mat4 &Mbox, const glm::mat4 &Mchunk ) const noexcept { - if (!blank::Intersection(box, Mbox, Bounds(), Mchunk)) { + float penetration; + glm::vec3 normal; + + if (!blank::Intersection(box, Mbox, Bounds(), Mchunk, penetration, normal)) { return false; } for (int idx = 0, z = 0; z < depth; ++z) { diff --git a/tst/model/GeometryTest.cpp b/tst/model/GeometryTest.cpp index 71830c6..82f88ee 100644 --- a/tst/model/GeometryTest.cpp +++ b/tst/model/GeometryTest.cpp @@ -64,6 +64,10 @@ void GeometryTest::testRayBoxIntersection() { } void GeometryTest::testBoxBoxIntersection() { + const float delta = std::numeric_limits::epsilon(); + float depth = 0; + glm::vec3 normal(0); + AABB box{ { -1, -1, -1 }, { 1, 1, 1 } }; // 2x2x2 cube centered around origin glm::mat4 Ma(1); // identity glm::mat4 Mb(1); // identity @@ -71,28 +75,43 @@ void GeometryTest::testBoxBoxIntersection() { CPPUNIT_ASSERT_MESSAGE( "identical OBBs don't intersect", - Intersection(box, Ma, box, Mb) + Intersection(box, Ma, box, Mb, depth, normal) + ); + // depth is two, but normal can be any + // (will probably be the first axis of box a, but any is valid) + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "penetration depth of coincidental 2x2x2 boxes is not 2", + 2.0f, depth, delta ); 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) + !Intersection(box, Ma, box, Mb, depth, normal) ); + // depth and normal undefined for non-intersecting objects 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 + // they should barely touch. intersect by about sqrt(2) - 1.4 if my head works CPPUNIT_ASSERT_MESSAGE( "OBBs don't intersect (one rotated by 45°)", - Intersection(box, Ma, box, Mb) + Intersection(box, Ma, box, Mb, depth, normal) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth (with rotation)", + 0.01421356237309504880f, depth, delta + ); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "bad intersection normal (with rotation)", + glm::vec3(1, 0, 0), abs(normal) // normal can be in + or - x, therefore abs() ); 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) + !Intersection(box, Ma, box, Mb, depth, normal) ); } -- 2.39.2