From: Daniel Karbach Date: Wed, 16 Mar 2016 14:35:25 +0000 (+0100) Subject: better ray/floor intersection algorithm X-Git-Url: http://git.localhorst.tv/?p=tacos.git;a=commitdiff_plain;h=0fc4efc1800c07534c1e945618630910e2a8e87f better ray/floor intersection algorithm it's somewhat better, but still very buggy --- diff --git a/src/world/world.cpp b/src/world/world.cpp index cbff100..b7037f0 100644 --- a/src/world/world.cpp +++ b/src/world/world.cpp @@ -214,11 +214,8 @@ void Floor::DrawVAO(int vao_x, int vao_z) const noexcept { } bool Floor::Intersection(const Ray &ray, glm::vec3 &point) { - // 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 + // see http://www.cse.yorku.ca/~amana/research/grid.pdf and + // http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml section Grid Traversal // cache 1/dir to avoid some conditionals and divisions glm::vec3 inverse_direction(ray.InverseDirection()); @@ -226,8 +223,11 @@ bool Floor::Intersection(const Ray &ray, glm::vec3 &point) { // 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; + // holds the distance along the ray to advance by one cell in each direction + glm::vec3 tDelta(glm::abs(inverse_direction)); + // holds the distance along the ray to the next cell boundary + // TODO: not sure if that is always correct (e.g. with negative components in ray direction) + glm::vec3 tMax(tDelta * (1.0f - glm::fract(ray.origin))); // 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; @@ -241,13 +241,15 @@ bool Floor::Intersection(const Ray &ray, glm::vec3 &point) { 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; + // TODO: not sure if this is correct, could be that contact has to be recalculated with + // outer planes instead of the -1 ones (that might actually also apply to cell calculation) + tMax.x = (float(cell.x) - contact.x) * inverse_direction.x; + tMax.z = (float(cell.y) - contact.z) * inverse_direction.z; } // step hold the direction we're traversing the grid @@ -276,74 +278,48 @@ bool Floor::Intersection(const Ray &ray, glm::vec3 &point) { return true; } } - //std::cout << " ray is vertical and outside of grid" << std::endl; return false; } // 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; + // 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; } - // okay, we're still above, advance to the next cell - if (x_near < z_near || std::isnan(z_near)) { + // advance to the next cell + if (tMax.x < tMax.z) { + tMax.x += tDelta.x; cell.x += step.x; } else { + tMax.z += tDelta.z; 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/world/FloorTest.cpp b/tst/world/FloorTest.cpp index 169dba8..396c065 100644 --- a/tst/world/FloorTest.cpp +++ b/tst/world/FloorTest.cpp @@ -4,8 +4,6 @@ #include -#include - CPPUNIT_TEST_SUITE_REGISTRATION(tacos::test::FloorTest); namespace tacos { @@ -136,7 +134,7 @@ void FloorTest::testIntersection() { 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 :(", + "weird ray #1 from interactive testing doesn't intersect :(", floor.Intersection(ray, point) ); AssertEqual( @@ -147,12 +145,12 @@ void FloorTest::testIntersection() { 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 :(", + "weird ray #2 from interactive testing doesn't intersect :(", floor.Intersection(ray, point) ); AssertEqual( "unexpected intersection point", - glm::vec3(15.17783f, 0.0f, 14.5698f), point, + glm::vec3(15.17783f, 0.0f, 14.56982f), point, 0.00001f ); }