]> git.localhorst.tv Git - tacos.git/commitdiff
better ray/floor intersection algorithm
authorDaniel Karbach <daniel.karbach@localhorst.tv>
Wed, 16 Mar 2016 14:35:25 +0000 (15:35 +0100)
committerDaniel Karbach <daniel.karbach@localhorst.tv>
Wed, 16 Mar 2016 14:35:25 +0000 (15:35 +0100)
it's somewhat better, but still very buggy

src/world/world.cpp
tst/world/FloorTest.cpp

index cbff1005b744a16d73bf7551f868076bfd20143b..b7037f0c157723ebc574d9416d15b277beeba7b1 100644 (file)
@@ -214,11 +214,8 @@ void Floor::DrawVAO(int vao_x, int vao_z) const noexcept {
 }
 
 bool Floor::Intersection(const Ray &ray, glm::vec3 &point) {
 }
 
 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());
 
        // 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));
 
        // 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;
 
        // 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
                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);
                        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
        }
 
        // step hold the direction we're traversing the grid
@@ -276,74 +278,48 @@ bool Floor::Intersection(const Ray &ray, glm::vec3 &point) {
                                return true;
                        }
                }
                                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];
 
                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);
        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 {
                        cell.x += step.x;
                } else {
+                       tMax.z += tDelta.z;
                        cell.y += step.y;
                }
        }
                        cell.y += step.y;
                }
        }
-       //std::cout << "        ray left grid at cell " << cell << std::endl;
-       // we left the grid, so no intersection
+
        return false;
 }
 
        return false;
 }
 
index 169dba84529ec3c32c60a3ecf6e67aadc5ed86f6..396c0651cc5c309ddba1b828e7dfc08dfe80b286 100644 (file)
@@ -4,8 +4,6 @@
 
 #include <world/Floor.hpp>
 
 
 #include <world/Floor.hpp>
 
-#include <glm/gtx/io.hpp>
-
 CPPUNIT_TEST_SUITE_REGISTRATION(tacos::test::FloorTest);
 
 namespace tacos {
 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(
        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(
                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(
        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",
                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
        );
 }
                0.00001f
        );
 }