From 9932ee17a767b64cb52c213e133c6b91a90a8dd2 Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Thu, 1 Dec 2016 12:09:43 +0100 Subject: [PATCH] spheres --- src/geometry/geometry.cpp | 39 +++++++++ src/geometry/primitive.hpp | 35 +++++++- tst/geometry/IntersectionTest.cpp | 130 +++++++++++++++++++++++++++++- tst/geometry/IntersectionTest.hpp | 16 ++-- 4 files changed, 210 insertions(+), 10 deletions(-) diff --git a/src/geometry/geometry.cpp b/src/geometry/geometry.cpp index 8deed86..1c1bfd6 100644 --- a/src/geometry/geometry.cpp +++ b/src/geometry/geometry.cpp @@ -217,6 +217,16 @@ std::ostream &operator <<(std::ostream &out, const Plane &plane) { return out << "Plane(" << plane.normal << ", " << plane.dist << ')'; } +float Distance(const glm::vec3 &point, const Plane &plane) { + return std::abs(SignedDistance(point, plane)); +} + +float SignedDistance(const glm::vec3 &point, const Plane &plane) { + return ( + plane.A() * point.x + plane.B() * point.y + plane.C() * point.z + plane.D() + ) / glm::length(plane.normal); +} + std::ostream &operator <<(std::ostream &out, const Frustum &frustum) { return out << "Frustum(" << std::endl << "\tleft: " << frustum.plane[0] << std::endl @@ -277,6 +287,35 @@ bool CullTest(const AABB &box, const Frustum &frustum) noexcept { } return false; } + +std::ostream &operator <<(std::ostream &out, const Sphere &s) { + return out << "Sphere(" << s.origin << ", " << s.radius << ')'; +} + +bool Intersection( + const Sphere &sphere, + const Plane &plane, + float &dist, + glm::vec3 &norm +) noexcept { + float sig_dist = SignedDistance(sphere.origin, plane); + dist = sphere.radius - std::abs(sig_dist); + if (dist > 0.0f) { + norm = sig_dist > 0.0f ? plane.normal : -plane.normal; + return true; + } else { + return false; + } +} + +bool Intersection( + const Sphere &sphere, + const Plane &plane, + float &dist +) noexcept { + dist = sphere.radius - SignedDistance(sphere.origin, plane); + return dist > 0.0f; } } +} diff --git a/src/geometry/primitive.hpp b/src/geometry/primitive.hpp index 4711306..819ef04 100644 --- a/src/geometry/primitive.hpp +++ b/src/geometry/primitive.hpp @@ -87,7 +87,8 @@ bool Intersection( float &depth, glm::vec3 &normal) noexcept; - +/// Plane defined by a surface norml and distance to the origin such that +/// the point (normal * dist) lies on the plane. struct Plane { glm::vec3 normal; float dist; @@ -115,6 +116,13 @@ struct Plane { std::ostream &operator <<(std::ostream &, const Plane &); +/// Shortest distance from point to plane. +float Distance(const glm::vec3 &point, const Plane &plane); +/// Shortest distance from point to plane with sign indicating whether +/// it's in front of (positive, in direction of normal) or behind +/// (negative, counter direction of normal) the surface. +float SignedDistance(const glm::vec3 &point, const Plane &plane); + struct Frustum { Plane plane[6]; Plane &Left() noexcept { return plane[0]; } @@ -154,6 +162,31 @@ std::ostream &operator <<(std::ostream &, const Frustum &); bool CullTest(const AABB &box, const glm::mat4 &) noexcept; bool CullTest(const AABB &box, const Frustum &) noexcept; +struct Sphere { + glm::vec3 origin; + float radius; +}; + +std::ostream &operator <<(std::ostream &, const Sphere &); + +/// Test for intersection of sphere with double sided infinite plane. +/// If true, dist will hold the smaller interpenetration depth and norm +/// the respective contact normal. +bool Intersection( + const Sphere &sphere, + const Plane &plane, + float &dist, + glm::vec3 &norm) noexcept; + +/// Test for intersection of sphere with half space defined by the +/// backface of given plane. +/// In all cases, dist will hold the distance between the near points +/// of plane and sphere. Contact normal will always be the plane's normal. +bool Intersection( + const Sphere &sphere, + const Plane &plane, + float &dist) noexcept; + } } diff --git a/tst/geometry/IntersectionTest.cpp b/tst/geometry/IntersectionTest.cpp index 7aac189..d2332fe 100644 --- a/tst/geometry/IntersectionTest.cpp +++ b/tst/geometry/IntersectionTest.cpp @@ -21,7 +21,7 @@ void IntersectionTest::tearDown() { } -void IntersectionTest::testSimpleRayBoxIntersection() { +void IntersectionTest::testSimpleRayBox() { 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 @@ -68,7 +68,7 @@ void IntersectionTest::testSimpleRayBoxIntersection() { ); } -void IntersectionTest::testRayBoxIntersection() { +void IntersectionTest::testRayBox() { 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 @@ -215,7 +215,7 @@ void IntersectionTest::testRayBoxIntersection() { ); } -void IntersectionTest::testBoxBoxIntersection() { +void IntersectionTest::testBoxBox() { const float delta = std::numeric_limits::epsilon(); float depth = 0; glm::vec3 normal(0); @@ -267,6 +267,130 @@ void IntersectionTest::testBoxBoxIntersection() { ); } +void IntersectionTest::testSpherePlane() { + const float delta = std::numeric_limits::epsilon(); + + // unit sphere at origin + Sphere sphere{{ 0.0f, 0.0f, 0.0f }, 1.0f}; + // horizontal plane at origin (the XZ plane) + Plane plane{{ 0.0f, 1.0f, 0.0f }, 0.0f }; + float depth; + glm::vec3 normal; + + CPPUNIT_ASSERT_MESSAGE( + "sphere at origin does not intersect plane at origin", + Intersection(sphere, plane, depth, normal) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with plane", + 1.0f, depth, delta + ); + // normal is actually undefined in this case, but either will work + CPPUNIT_ASSERT_MESSAGE( + "bad contact normal of sphere intersecting plane", + normal == glm::vec3(0.0f, 1.0f, 0.0f) || normal == glm::vec3(0.0f, -1.0f, 0.0f) + ); + + // center above, but still intersecting + sphere.origin.y = 0.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere does not intersect plane", + Intersection(sphere, plane, depth, normal) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with plane", + 0.5f, depth, delta + ); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "bad contact normal of sphere intersecting plane", + glm::vec3(0.0f, 1.0f, 0.0f), normal + ); + + // center below, but still intersecting + sphere.origin.y = -0.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere does not intersect plane", + Intersection(sphere, plane, depth, normal) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with plane", + 0.5f, depth, delta + ); + CPPUNIT_ASSERT_EQUAL_MESSAGE( + "bad contact normal of sphere intersecting plane", + glm::vec3(0.0f, -1.0f, 0.0f), normal + ); + + // sphere completely above + sphere.origin.y = 1.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere above plane intersects", + !Intersection(sphere, plane, depth, normal) + ); + + // sphere completely below + sphere.origin.y = -1.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere below plane intersects", + !Intersection(sphere, plane, depth, normal) + ); +} + +void IntersectionTest::testSphereHalfSpace() { + const float delta = std::numeric_limits::epsilon(); + + // unit sphere at origin + Sphere sphere{{ 0.0f, 0.0f, 0.0f }, 1.0f}; + // horizontal plane at origin (the XZ plane) + Plane plane{{ 0.0f, 1.0f, 0.0f }, 0.0f }; + float depth; + + CPPUNIT_ASSERT_MESSAGE( + "sphere at origin does not intersect half space to origin", + Intersection(sphere, plane, depth) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with half space", + 1.0f, depth, delta + ); + + sphere.origin.y = 0.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere does not intersect half space", + Intersection(sphere, plane, depth) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with half space", + 0.5f, depth, delta + ); + + sphere.origin.y = -0.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere does not intersect half space", + Intersection(sphere, plane, depth) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with half space", + 1.5f, depth, delta + ); + + sphere.origin.y = -1.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere inside half space does not intersect", + Intersection(sphere, plane, depth) + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + "bad penetration depth of sphere with half space", + 2.5f, depth, delta + ); + + sphere.origin.y = 1.5f; + CPPUNIT_ASSERT_MESSAGE( + "sphere outside half space intersects", + !Intersection(sphere, plane, depth) + ); +} + } } } diff --git a/tst/geometry/IntersectionTest.hpp b/tst/geometry/IntersectionTest.hpp index 19c25e6..d0c7d80 100644 --- a/tst/geometry/IntersectionTest.hpp +++ b/tst/geometry/IntersectionTest.hpp @@ -13,9 +13,11 @@ class IntersectionTest CPPUNIT_TEST_SUITE(IntersectionTest); -CPPUNIT_TEST(testSimpleRayBoxIntersection); -CPPUNIT_TEST(testRayBoxIntersection); -CPPUNIT_TEST(testBoxBoxIntersection); +CPPUNIT_TEST(testSimpleRayBox); +CPPUNIT_TEST(testRayBox); +CPPUNIT_TEST(testBoxBox); +CPPUNIT_TEST(testSpherePlane); +CPPUNIT_TEST(testSphereHalfSpace); CPPUNIT_TEST_SUITE_END(); @@ -23,9 +25,11 @@ public: void setUp(); void tearDown(); - void testSimpleRayBoxIntersection(); - void testRayBoxIntersection(); - void testBoxBoxIntersection(); + void testSimpleRayBox(); + void testRayBox(); + void testBoxBox(); + void testSpherePlane(); + void testSphereHalfSpace(); }; -- 2.39.2