}
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());
// 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;
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
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;
}
#include <world/Floor.hpp>
-#include <glm/gtx/io.hpp>
-
CPPUNIT_TEST_SUITE_REGISTRATION(tacos::test::FloorTest);
namespace tacos {
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(
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
);
}
projects / tacos.git / commitdiff