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
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)
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);
}
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; }
private:
int width;
int height;
+ glm::vec2 inverse_size;
float fov;
float aspect;
--- /dev/null
+#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<float>::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<float>::epsilon();
+}
+
+}
#ifndef TACOS_PHYSICS_RAY_HPP_
#define TACOS_PHYSICS_RAY_HPP_
+#include <limits>
#include <glm/glm.hpp>
glm::vec3 origin;
glm::vec3 direction;
+ glm::vec3 InverseDirection() const noexcept {
+ return glm::vec3(
+ std::fabs(direction.x) < std::numeric_limits<float>::epsilon()
+ ? std::numeric_limits<float>::infinity()
+ : 1.0f / direction.x,
+ std::fabs(direction.y) < std::numeric_limits<float>::epsilon()
+ ? std::numeric_limits<float>::infinity()
+ : 1.0f / direction.y,
+ std::fabs(direction.z) < std::numeric_limits<float>::epsilon()
+ ? std::numeric_limits<float>::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
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));
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
#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;
}
}
+#include "app/config.hpp"
+#include "app/init.hpp"
+#include "graphics/window.hpp"
+
#include <cppunit/extensions/TestFactoryRegistry.h>
#include <cppunit/ui/text/TestRunner.h>
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());
--- /dev/null
+#include "vector_assert.hpp"
+
+#include <cppunit/extensions/HelperMacros.h>
+
+
+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
+ );
+}
+
+}
+}
--- /dev/null
+#ifndef TACOS_TEST_VECTOR_ASSERT_HPP_
+#define TACOS_TEST_VECTOR_ASSERT_HPP_
+
+#include <limits>
+#include <string>
+#include <glm/glm.hpp>
+
+
+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<float>::epsilon());
+
+}
+}
+
+#endif
--- /dev/null
+#include "FloorTest.hpp"
+
+#include "../vector_assert.hpp"
+
+#include <world/Floor.hpp>
+
+#include <glm/gtx/io.hpp>
+
+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
+ );
+}
+
+}
+}
--- /dev/null
+#ifndef TACOS_TEST_WORLD_FLOORTEST_HPP_
+#define TACOS_TEST_WORLD_FLOORTEST_HPP_
+
+#include <cppunit/extensions/HelperMacros.h>
+
+
+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
projects / tacos.git / commitdiff