From: Daniel Karbach Date: Fri, 11 Mar 2016 16:00:02 +0000 (+0100) Subject: ray/floor intersection experiments X-Git-Url: http://git.localhorst.tv/?p=tacos.git;a=commitdiff_plain;h=57f81dc2a126e77e48e8962a9d6730c59ffddbda ray/floor intersection experiments --- diff --git a/Makefile b/Makefile index f491d89..b388921 100644 --- a/Makefile +++ b/Makefile @@ -19,7 +19,7 @@ LDXXFLAGS += $(PKGLIBS) DEBUG_FLAGS = -g3 -O0 PROFILE_FLAGS = -DNDEBUG -O1 -g3 RELEASE_FLAGS = -DNDEBUG -O2 -g1 -TEST_FLAGS = -g -O2 -I./src $(TESTFLAGS) +TEST_FLAGS = -g -O1 -I./src $(TESTFLAGS) SOURCE_DIR := src TEST_SRC_DIR := tst diff --git a/src/graphics/viewport.cpp b/src/graphics/viewport.cpp index 17c99c7..4ff2792 100644 --- a/src/graphics/viewport.cpp +++ b/src/graphics/viewport.cpp @@ -9,6 +9,7 @@ namespace tacos { Viewport::Viewport(int w, int h) : width(w) , height(h) +, inverse_size(1.0f / float(width), 1.0f / float(height)) , fov(0.78539816339744830961f) // π/4 , aspect(float(w) / float(h)) , near(0.1f) @@ -21,9 +22,12 @@ Viewport::Viewport(int w, int h) void Viewport::Resize(int w, int h) noexcept { width = w; height = h; - aspect = float(width) / float(height); + float fw = float(w), fh = float(h); + inverse_size.x = 1.0f / fw; + inverse_size.y = 1.0f / fh; + aspect = fw / fh; perspective = glm::perspective(fov, aspect, near, far); - ortho = glm::ortho(0.0f, float(width), float(height), 0.0f, near, far); + ortho = glm::ortho(0.0f, fw, fh, 0.0f, near, far); glViewport(0, 0, width, height); } diff --git a/src/graphics/viewport.hpp b/src/graphics/viewport.hpp index cc9a100..e9330c5 100644 --- a/src/graphics/viewport.hpp +++ b/src/graphics/viewport.hpp @@ -18,6 +18,7 @@ public: int Width() const noexcept { return width; } int Height() const noexcept { return height; } + glm::vec2 InverseSize() const noexcept { return inverse_size; } const glm::mat4 &Perspective() const noexcept { return perspective; } const glm::mat4 &Ortho() const noexcept { return ortho; } @@ -25,6 +26,7 @@ public: private: int width; int height; + glm::vec2 inverse_size; float fov; float aspect; diff --git a/src/physics/ray.cpp b/src/physics/ray.cpp new file mode 100644 index 0000000..89ea5d7 --- /dev/null +++ b/src/physics/ray.cpp @@ -0,0 +1,43 @@ +#include "ray.hpp" + + +namespace tacos { + +bool TriangleIntersection( + const Ray &ray, + const glm::vec3 &p0, + const glm::vec3 &p1, + const glm::vec3 &p2, + glm::vec3 &point +) noexcept { + glm::vec3 edge1(p1 - p0); + glm::vec3 edge2(p2 - p0); + + glm::vec3 h(glm::cross(ray.direction, edge2)); + float a = glm::dot(edge1, h); + + if (std::fabs(a) < std::numeric_limits::epsilon()) { + return false; + } + + float f = 1.0f / a; + glm::vec3 s(ray.origin - p0); + float u = f * glm::dot(s, h); + + if (u < 0.0f || u > 1.0f) { + return false; + } + + glm::vec3 q(glm::cross(s, edge1)); + float v = f * glm::dot(ray.direction, q); + + if (v < 0.0f || u + v > 1.0f) { + return false; + } + + float t = f * glm::dot(edge2, q); + point = ray.origin + (t * ray.direction); + return t > std::numeric_limits::epsilon(); +} + +} diff --git a/src/physics/ray.hpp b/src/physics/ray.hpp index 355af50..22d19c4 100644 --- a/src/physics/ray.hpp +++ b/src/physics/ray.hpp @@ -1,6 +1,7 @@ #ifndef TACOS_PHYSICS_RAY_HPP_ #define TACOS_PHYSICS_RAY_HPP_ +#include #include @@ -11,8 +12,30 @@ struct Ray { glm::vec3 origin; glm::vec3 direction; + glm::vec3 InverseDirection() const noexcept { + return glm::vec3( + std::fabs(direction.x) < std::numeric_limits::epsilon() + ? std::numeric_limits::infinity() + : 1.0f / direction.x, + std::fabs(direction.y) < std::numeric_limits::epsilon() + ? std::numeric_limits::infinity() + : 1.0f / direction.y, + std::fabs(direction.z) < std::numeric_limits::epsilon() + ? std::numeric_limits::infinity() + : 1.0f / direction.z); + } + }; +/// check whether given ray intersects with the triangle with vertices p0, p1, and p2 +/// point of intersection is writte to point if the result is positive +bool TriangleIntersection( + const Ray &ray, + const glm::vec3 &p0, + const glm::vec3 &p1, + const glm::vec3 &p2, + glm::vec3 &point) noexcept; + } #endif diff --git a/src/tacos.cpp b/src/tacos.cpp index e477ab4..fe1c7aa 100644 --- a/src/tacos.cpp +++ b/src/tacos.cpp @@ -218,7 +218,7 @@ int main(int argc, char *argv[]) { VP = viewport.Perspective() * V; { // mouse inverse_VP = glm::inverse(VP); - glm::vec2 clip_mouse((screen_mouse / glm::vec2(viewport.Width(), viewport.Height()) - 0.5f) * 2.0f); + glm::vec2 clip_mouse((screen_mouse * viewport.InverseSize() - 0.5f) * 2.0f); // viewport space has origin in lower left, but sdl gives coordinates with orgin in upper left, // so Y is inverted here (since it maps from -1 to 1 simply by negating) glm::vec4 ray_begin(inverse_VP * glm::vec4(clip_mouse.x, -clip_mouse.y, -1.0f, 1.0f)); @@ -227,10 +227,13 @@ int main(int argc, char *argv[]) { world_mouse.direction = glm::normalize((glm::vec3(ray_end) / ray_end.w) - world_mouse.origin); } + //std::cout << "ray " << world_mouse.origin << ", " << world_mouse.direction << std::endl; if (floor.Intersection(world_mouse, pointer)) { cursor.FloorTile(floor, int(pointer.x), int(pointer.z)); + //std::cout << " +++ intersecting at " << pointer << std::endl; } else { cursor.Hide(); + //std::cout << " --- not intersecting" << std::endl; } // render diff --git a/src/world/world.cpp b/src/world/world.cpp index 25723ba..cbff100 100644 --- a/src/world/world.cpp +++ b/src/world/world.cpp @@ -1,6 +1,9 @@ #include "Cursor.hpp" #include "Floor.hpp" +#include +#include + namespace tacos { @@ -211,20 +214,137 @@ void Floor::DrawVAO(int vao_x, int vao_z) const noexcept { } bool Floor::Intersection(const Ray &ray, glm::vec3 &point) { - // TODO: this tests for Y=0 plane intersection, change to respect heightmap - if (std::abs(ray.direction.y) < std::numeric_limits::epsilon()) { - // ray parallel to plane - return false; + // see http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml section Grid Traversal + + // TODO: somehow this is not reliable at all, maybe due to numeric inaccuracy + // the result is determined by checking the ray against triangles and it's + // possible that it sometimes slips through the theoratically inexistant seams + + // cache 1/dir to avoid some conditionals and divisions + glm::vec3 inverse_direction(ray.InverseDirection()); + + // cell indicates the current tile we're considering + glm::ivec2 cell(int(ray.origin.x), int(ray.origin.z)); + + // store the previous height to check against the lower of cell entry and exit + float prev_height = ray.origin.y; + + // if ray's origin is outside the grid, advance to the first cell it hits + float x_near, x_far, z_near, z_far, t_min, t_max; + if (cell.x < 0 || cell.x >= width || cell.y < 0 || cell.y >= depth) { + x_near = (-ray.origin.x) * inverse_direction.x; + // subtracting one so the point is in the last cell, rather than after it, when approaching from the far end + x_far = (width - 1 - ray.origin.x) * inverse_direction.x; + z_near = (-ray.origin.z) * inverse_direction.z; + z_far = (depth - 1 - ray.origin.z) * inverse_direction.z; + t_min = std::max(std::min(x_near, x_far), std::min(z_near, z_far)); + t_max = std::min(std::max(x_near, x_far), std::max(z_near, z_far)); + if (t_max < 0.0f || t_min > t_max) { + // ray doesn't touch our grid at all + //std::cout << " ray does not touch grid" << std::endl; + return false; + } + glm::vec3 contact = ray.origin + t_min * ray.direction; + cell.x = int(contact.x); + cell.y = int(contact.z); + prev_height = contact.y; } - float factor = ray.origin.y / ray.direction.y; - if (factor > 0.0f) { - // intersection "behind" the ray + + // step hold the direction we're traversing the grid + glm::ivec2 step(glm::sign(ray.direction.x), glm::sign(ray.direction.z)); + + if (step.x == 0 && step.y == 0) { + // ray shoots straight up or down + // check the current cell (if it's valid) + if (cell.x >= 0 && cell.x < width && cell.y >= 0 && cell.y < depth) { + if (TriangleIntersection( + ray, + glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 0), float(cell.y + 0)), + glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 0), float(cell.y + 0)), + glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 1), float(cell.y + 1)), + point + )) { + return true; + } + if (TriangleIntersection( + ray, + glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 0), float(cell.y + 0)), + glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 1), float(cell.y + 1)), + glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 1), float(cell.y + 1)), + point + )) { + return true; + } + } + //std::cout << " ray is vertical and outside of grid" << std::endl; return false; } - point.x = ray.origin.x - (ray.direction.x * factor); - point.y = 0.0f; - point.z = ray.origin.z - (ray.direction.z * factor); - return point.x >= 0.0f && point.x <= float(width) && point.z >= 0.0f && point.z <= float(depth); + + // cache for the height of the vertices of the current cell + float height[4]; + + // now step through each cell until Y gets below the surface or one of X or Z exit the grid bounds + while (cell.x >= 0 && cell.x < width && cell.y >= 0 && cell.y < depth) { + // pull heights for the current cell + height[0] = GetElevation(cell.x + 0, cell.y + 0); + height[1] = GetElevation(cell.x + 1, cell.y + 0); + height[2] = GetElevation(cell.x + 0, cell.y + 1); + height[3] = GetElevation(cell.x + 1, cell.y + 1); + // highest point in the cell + float max_height = std::max(std::max(height[0], height[1]), std::max(height[2], height[3])); + + // check where the ray exits the current cell + // test how far away the ray is from each plane and choose the closest + x_near = (float(cell.x + step.x) - ray.origin.x) * inverse_direction.x; + z_near = (float(cell.y + step.y) - ray.origin.z) * inverse_direction.z; + // if dir is 0, inverse dir is infinity. multiplying 0 by infinity is NaN. min(x, inf) is x, min(x, nan) is x + t_min = std::min(x_near, z_near); + // heightof the ray at exit + float cur_height = ray.origin.y + (t_min * ray.direction.y); + // lowest point of the ray in the cell + float ray_low = std::min(prev_height, cur_height); + // store exit height for next cell's entry height + prev_height = cur_height; + + // check if we might end up below the surface + // if this is true, there still could be no intersection if the ray is close to parallel to the surface + // or due to precision issues, which are currently biting me + if (ray_low < max_height) { + // possibly, so check individual surfaces + // the triangles used for rendering are (x,z), (x+1,z), (x,z+1) and + // (x+1,z),(x+1,z+1), (x,z+1), so height indices 012 and 132 + if (TriangleIntersection( + ray, + glm::vec3(float(cell.x + 0), height[0], float(cell.y + 0)), + glm::vec3(float(cell.x + 1), height[1], float(cell.y + 0)), + glm::vec3(float(cell.x + 0), height[2], float(cell.y + 1)), + point + )) { + return true; + } + if (TriangleIntersection( + ray, + glm::vec3(float(cell.x + 1), height[1], float(cell.y + 0)), + glm::vec3(float(cell.x + 1), height[3], float(cell.y + 1)), + glm::vec3(float(cell.x + 0), height[2], float(cell.y + 1)), + point + )) { + return true; + } + // hmm, maybe I should check against planes and if true test if the XZ of the intersection points + // lie within their corresponding half-square with some flexibility and somehow pick the right one + //std::cout << " ray got below max floor height at cell " << cell << " but did not intersect a triangle" << std::endl; + } + // okay, we're still above, advance to the next cell + if (x_near < z_near || std::isnan(z_near)) { + cell.x += step.x; + } else { + cell.y += step.y; + } + } + //std::cout << " ray left grid at cell " << cell << std::endl; + // we left the grid, so no intersection + return false; } } diff --git a/tst/test.cpp b/tst/test.cpp index ff1ce71..a8f5a7e 100644 --- a/tst/test.cpp +++ b/tst/test.cpp @@ -1,3 +1,7 @@ +#include "app/config.hpp" +#include "app/init.hpp" +#include "graphics/window.hpp" + #include #include @@ -6,6 +10,11 @@ using CppUnit::TextUi::TestRunner; int main(int, char **) { + // need GL context because some tests depend it (by accident) + tacos::Config config; + tacos::Init init(config); + tacos::Window window(100, 100); + TestRunner runner; TestFactoryRegistry ®istry = TestFactoryRegistry::getRegistry(); runner.addTest(registry.makeTest()); diff --git a/tst/vector_assert.cpp b/tst/vector_assert.cpp new file mode 100644 index 0000000..e15e209 --- /dev/null +++ b/tst/vector_assert.cpp @@ -0,0 +1,31 @@ +#include "vector_assert.hpp" + +#include + + +namespace tacos { +namespace test { + +/// assert that given vectors are equal enough according to given epsilon +void AssertEqual( + const std::string &message, + const glm::vec3 &expected, + const glm::vec3 &actual, + float epsilon +) { + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + message + " (X component)", + expected.x, actual.x, epsilon + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + message + " (Y component)", + expected.y, actual.y, epsilon + ); + CPPUNIT_ASSERT_DOUBLES_EQUAL_MESSAGE( + message + " (Z component)", + expected.z, actual.z, epsilon + ); +} + +} +} diff --git a/tst/vector_assert.hpp b/tst/vector_assert.hpp new file mode 100644 index 0000000..12602c5 --- /dev/null +++ b/tst/vector_assert.hpp @@ -0,0 +1,22 @@ +#ifndef TACOS_TEST_VECTOR_ASSERT_HPP_ +#define TACOS_TEST_VECTOR_ASSERT_HPP_ + +#include +#include +#include + + +namespace tacos { +namespace test { + +/// assert that given vectors are equal enough according to given epsilon +void AssertEqual( + const std::string &message, + const glm::vec3 &expected, + const glm::vec3 &actual, + float epsilon = std::numeric_limits::epsilon()); + +} +} + +#endif diff --git a/tst/world/FloorTest.cpp b/tst/world/FloorTest.cpp new file mode 100644 index 0000000..169dba8 --- /dev/null +++ b/tst/world/FloorTest.cpp @@ -0,0 +1,161 @@ +#include "FloorTest.hpp" + +#include "../vector_assert.hpp" + +#include + +#include + +CPPUNIT_TEST_SUITE_REGISTRATION(tacos::test::FloorTest); + +namespace tacos { +namespace test { + +void FloorTest::setUp() { +} + +void FloorTest::tearDown() { +} + + +void FloorTest::testIntersection() { + Floor floor(33, 33); + Ray ray; + glm::vec3 point; + + // default floor has all heights at 0, so a ray within the grid at height 1 pointing + // straight down should intersect it + // this ray hits the triangle somewhere near the middle + ray.origin = glm::vec3(0.5f, 1.0f, 0.75f); + ray.direction = glm::vec3(0.0f, -1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing down at a triangle does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(0.5f, 0.0f, 0.75f), point + ); + // this ray should hit on the low X edge of the triangle + ray.origin = glm::vec3(0.0f, 1.0f, 0.5f); + ray.direction = glm::vec3(0.0f, -1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing down at a low X triangle edge does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(0.0f, 0.0f, 0.5f), point + ); + // this ray should hit on the low Z edge of the triangle + ray.origin = glm::vec3(0.5f, 1.0f, 0.0f); + ray.direction = glm::vec3(0.0f, -1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing down at a low Z triangle edgedoes not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(0.5f, 0.0f, 0.0f), point + ); + // this ray should hit on the diagonal edge of the triangle + ray.origin = glm::vec3(0.5f, 1.0f, 0.5f); + ray.direction = glm::vec3(0.0f, -1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing down at a diagonal triangle edgedoes not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(0.5f, 0.0f, 0.5f), point + ); + // this ray points straight away from the floor, so should not intersect + ray.origin = glm::vec3(0.5f, 1.0f, 0.5f); + ray.direction = glm::vec3(0.0f, 1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing up intersects floor when it shouldn't", + !floor.Intersection(ray, point) + ); + // this ray start below the floor and points down, so stays "underground" the whole time + ray.origin = glm::vec3(0.5f, -1.0f, 0.5f); + ray.direction = glm::vec3(0.0f, -1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray pointing down intersects floor when it shouldn't", + !floor.Intersection(ray, point) + ); + // this ray start below the floor and points up, that means it intersects, although from the unexpected side + ray.origin = glm::vec3(0.5f, -1.0f, 0.5f); + ray.direction = glm::vec3(0.0f, 1.0f, 0.0f); + CPPUNIT_ASSERT_MESSAGE( + "ray below the floor pointing up does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(0.5f, 0.0f, 0.5f), point + ); + + ray.origin = glm::vec3(0.0f, 1.0f, 1.0f); + ray.direction = glm::normalize(glm::vec3(1.0f, -1.0f, 0.0f)); + CPPUNIT_ASSERT_MESSAGE( + "diagonal ray, starts 1 unit above the floor and points down and to the right does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(1.0f, 0.0f, 1.0f), point + ); + // the same ray, but with origin outside the XZ grid + ray.origin = glm::vec3(-1.0f, 2.0f, 1.0f); + ray.direction = glm::normalize(glm::vec3(1.0f, -1.0f, 0.0f)); + CPPUNIT_ASSERT_MESSAGE( + "ray entering from the left does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(1.0f, 0.0f, 1.0f), point + ); + ray.origin = glm::vec3(3.0f, 2.0f, 1.0f); + ray.direction = glm::normalize(glm::vec3(-1.0f, -1.0f, 0.0f)); + CPPUNIT_ASSERT_MESSAGE( + "ray entering from the right does not intersect floor when it should", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(1.0f, 0.0f, 1.0f), point + ); + ray.origin = glm::vec3(1.0f, 1.0f, 1.0f); + ray.direction = glm::normalize(glm::vec3(1.0f, 0.0f, 1.0f)); + CPPUNIT_ASSERT_MESSAGE( + "ray parallel to the floor intersects floor when it shouldn't", + !floor.Intersection(ray, point) + ); + + ray.origin = glm::vec3(19.993f, 49.947f, 106.518f); + ray.direction = glm::normalize(glm::vec3(-0.07f, -0.528f, -0.846f)); + CPPUNIT_ASSERT_MESSAGE( + "weird ray from interactive testing doesn't intersect :(", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(13.37123870f, 0.0f, 26.48928486f), point, + 0.00001f // using custom delta since values above are somewhat rounded/truncated + ); + ray.origin = glm::vec3(19.995f, 49.952f, 106.515f); + ray.direction = glm::normalize(glm::vec3(-0.046f, -0.477f, -0.878f)); + CPPUNIT_ASSERT_MESSAGE( + "weird ray from interactive testing doesn't intersect :(", + floor.Intersection(ray, point) + ); + AssertEqual( + "unexpected intersection point", + glm::vec3(15.17783f, 0.0f, 14.5698f), point, + 0.00001f + ); +} + +} +} diff --git a/tst/world/FloorTest.hpp b/tst/world/FloorTest.hpp new file mode 100644 index 0000000..4fceee2 --- /dev/null +++ b/tst/world/FloorTest.hpp @@ -0,0 +1,30 @@ +#ifndef TACOS_TEST_WORLD_FLOORTEST_HPP_ +#define TACOS_TEST_WORLD_FLOORTEST_HPP_ + +#include + + +namespace tacos { +namespace test { + +class FloorTest +: public CppUnit::TestFixture { + +CPPUNIT_TEST_SUITE(FloorTest); + +CPPUNIT_TEST(testIntersection); + +CPPUNIT_TEST_SUITE_END(); + +public: + void setUp(); + void tearDown(); + + void testIntersection(); + +}; + +} +} + +#endif