#include "Cursor.hpp"
#include "Floor.hpp"
+#include <iostream>
+#include <glm/gtx/io.hpp>
+
namespace tacos {
}
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<float>::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;
}
}
projects / tacos.git / blobdiff