1 files changed, 101 insertions, 0 deletions
diff --git a/src/world.cpp b/src/world.cpp
index 3d21789..dc35f46 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -277,6 +277,107 @@ bool world_t::test_rect(const cmodel_t *cmodel, const entity_t *ignore)
 	return false;
 }
 
+static const v2f_t transforms[4] = {
+	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
+};
+
+static const tile_index_t transforms_index[4] = {
+	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
+};
+
+static const tile_index_t offsets_index[4] = {
+	{0, 0}, {-1, 0}, {-1, -1}, {0, -1}
+};
+
+static inline size_t quadrant(v2f_t dx)
+{
+	if (dx[0] == 0.0f && dx[1] == 0.0f)
+		return 4;
+
+	if (dx[1] >= 0.0f) {
+		if (dx[0] >= 0.0f)
+			return 0;
+		else
+			return 1;
+	} else {
+		if (dx[0] >= 0.0f)
+			return 3;
+		else
+			return 2;
+	}
+}
+
+trace_t world_t::trace(v2f_t start, v2f_t end, cflags_t cflags)
+{
+	v2f_t x, dx;
+	size_t quad;
+	trace_t res;
+
+	dx = end - start;
+
+	quad = quadrant(dx);
+	if (quad == 4) {
+		res.hit = false;
+		res.end = end;
+		res.frac = 1.0f;
+		return res;
+	}
+
+	start ^= transforms[quad];
+	dx ^= transforms[quad];
+	end ^= transforms[quad];
+
+	x = start;
+
+	while (1) {
+		v2f_t mod, P;
+		tile_index_t index;
+
+		if (x[0] >= end[0] && x[1] >= end[1]) {
+			res.hit = false;
+			res.end = end ^ transforms[quad];
+			res.frac = 1.0f;
+			return res;
+		}
+
+		index = (tile_index_t(x.floor()) ^ transforms_index[quad]) +
+		        offsets_index[quad];
+		//rectf_t tile(index, (v2f_t)index + v2f_t(1, 1));
+
+		if (get_tile(index, false)->type > cflags) { // FIXME
+			//debug_render->render_hlrect(tile, sf::Color::Red);
+			res.hit = true;
+			res.end = x ^ transforms[quad];
+			res.frac = (x - start).len() / (end - start).len();
+			return res;
+		}
+
+		mod = x - x.floor();
+		//debug_render->render_hlrect(tile, sf::Color::Green);
+
+		// Project onto x = const.
+		P[0] = 1.0f - mod[0];
+		P[1] = P[0] / dx[0] * dx[1];
+		if (mod[1] + P[1] >= 0.0f && mod[1] + P[1] <= 1.0f)
+		{
+			x += P;
+			x[0] = std::round(x[0]);
+			continue;
+		}
+
+		// Project onto y = const.
+		P[1] = 1.0f - mod[1];
+		P[0] = P[1] / dx[1] * dx[0];
+		x += P;
+		x[1] = std::round(x[1]);
+	}
+}
+
+trace_t trace_cmodel(v2f_t start, v2f_t end, const cmodel_t *cmodel)
+{
+	// TODO
+}
+
 void world_t::debug_point(sf::Vector2f point)
 {
 	sector_index_t index = sector_index_at(point);