From 8145afa69c7dd611850e521a557dc082a21e9e02 Mon Sep 17 00:00:00 2001 From: Robert Vollmert Date: Thu, 29 Oct 2009 23:31:45 +0100 Subject: Add simple 2d geometry library. Its point is to allow intersecting rays with grid lines and advancing rays from one cell to the next. --- crawl-ref/source/geom2d.cc | 149 ++++++++++++++++++++++++++++++++++++++++++ crawl-ref/source/geom2d.h | 84 ++++++++++++++++++++++++ crawl-ref/source/makefile.obj | 1 + 3 files changed, 234 insertions(+) create mode 100644 crawl-ref/source/geom2d.cc create mode 100644 crawl-ref/source/geom2d.h (limited to 'crawl-ref') diff --git a/crawl-ref/source/geom2d.cc b/crawl-ref/source/geom2d.cc new file mode 100644 index 0000000000..ddb2ec771d --- /dev/null +++ b/crawl-ref/source/geom2d.cc @@ -0,0 +1,149 @@ +/* + * File: geom2d.cc + * Summary: Plane geometry for shooting rays. + */ + +#include "AppHdr.h" +#include "debug.h" +#include "geom2d.h" + +#include + +namespace geom { + +static bool double_is_zero(double d) +{ + return (std::abs(d) < 0.0000001); +} + +// Is v parallel to the kernel of f? +static bool parallel(vector v, form f) +{ + return (double_is_zero(f(v))); +} + +vector ray::shoot(double t) const +{ + return (start + dir * t); +} + +void ray::advance(double t) +{ + start = shoot(t); +} + +// Determine the value of t such that +// r.start + t * r.dir lies on the line l. +// r and l must not be parallel. +double intersect(const ray &r, const line &l) +{ + ASSERT(!parallel(r.dir, l.f)); + double fp = l.f(r.start); + double fd = l.f(r.dir); + double t = (l.val - fp) / fd; + return (t); +} + +// Find the next intersection of r with a line in ls. +double nextintersect(const ray &r, const lineseq &ls) +{ + // ray must not be parallel to the lines + ASSERT(!parallel(r.dir, ls.f)); + double fp = ls.f(r.start); + double fd = ls.f(r.dir); + // want smallest positive t with + // fp + t*fd = ls.offset + k*ls.dist, k integral + double a = (fp - ls.offset) / ls.dist; + double k = (ls.dist*fd) > 0 ? ceil(a) : floor(a); + double t = (k - a) * ls.dist / fd; + return (t); +} + +// Line distance in the ray parameter. +// ls.f(r.shoot(tdist)) == ls.f(r.start) +- ls.dist +static double tdist(const ray &r, const lineseq &ls) +{ + ASSERT(!parallel(r.dir, ls.f)); + return (std::abs(ls.dist / ls.f(r.dir))); +} + +// Shoot the ray inside the next cell. +// Returns whether it hit a corner of the grid. +bool nextcell(ray &r, const grid &g, bool pass_corner) +{ + // XXX: ASSERT(!parallel(g.vert, g.horiz)); + lineseq ls; + if (parallel(r.dir, g.ls1.f)) + ls = g.ls2; + else if (parallel(r.dir, g.ls2.f)) + ls = g.ls1; + else + { + double s = nextintersect(r, g.ls1); + double t = nextintersect(r, g.ls2); + double sd = tdist(r, g.ls1); + double td = tdist(r, g.ls2); + if (double_is_zero(s - t)) + { + // Hitting the corner. + r.advance(s); + double u = std::min(sd, td); + if (pass_corner) + r.advance(0.5 * u); + else + { + // XXX: fudge ray into off-diagonal cell. + r.start.x += 0.001 * u * r.dir.y; + r.start.y += -0.001 * u * r.dir.x; + } + return (true); + } + double dmin = std::min(s,t); + double dnext = std::min(std::max(s,t), dmin + std::min(sd, td)); + r.advance((dmin + dnext) / 2.0); + return (false); + } + // advance an extra half + double s = nextintersect(r, ls); + r.advance(s + 0.5 * tdist(r, ls)); + return (false); +} + + +// vector space implementation + +const vector& vector::operator+=(const vector &v) +{ + x += v.x; + y += v.y; + return (*this); +} + +vector vector::operator+(const vector &v) const +{ + vector copy = *this; + copy += v; + return (copy); +} + +const vector& vector::operator*=(double t) +{ + x *= t; + y *= t; + return (*this); +} + +vector vector::operator*(double t) const +{ + vector copy = *this; + copy *= t; + return (copy); +} + +double form::operator()(const vector& v) const +{ + return (a*v.x + b*v.y); +} + +} + diff --git a/crawl-ref/source/geom2d.h b/crawl-ref/source/geom2d.h new file mode 100644 index 0000000000..d65ea06842 --- /dev/null +++ b/crawl-ref/source/geom2d.h @@ -0,0 +1,84 @@ +#ifndef GEOM2D_H +#define GEOM2D_H + +namespace geom { + +struct vector +{ + double x; + double y; + + vector(double _x = 0.0, double _y = 0.0) + : x(_x), y(_y) {} + + const vector& operator+=(const vector &v); + vector operator+(const vector &v) const; + const vector& operator*=(double t); + vector operator*(double t) const; +}; + +struct form +{ + double a; + double b; + + form(double _a = 0.0, double _b = 0.0) + : a(_a), b(_b) {} + + double operator()(const vector &v) const; +}; + +// A ray in two-dimensional space given by starting point +// and direction vector. +// The points of R are start + t*dir. +struct ray +{ + vector start; + vector dir; + + ray() {} + ray(double x0, double y0, double xd, double yd) + : start(x0, y0), dir(xd, yd) {} + + vector shoot(double t) const; + void advance(double t); +}; + +// A line in two-dimensional space as the preimage of a number +// under a linear form. L = form^{-1}(val). +struct line +{ + form f; + double val; +}; + +// A sequence of evenly spaced parallel lines, like the +// horizontal or vertical lines in a grid. +// Lines are f^{-1}(offset + k*dist) for integers k. +struct lineseq +{ + form f; + double offset; + double dist; + + lineseq() {} + lineseq(double a, double b, double o, double d) + : f(a,b), offset(o), dist(d) {} +}; + +struct grid +{ + lineseq ls1; + lineseq ls2; + + grid(lineseq l1, lineseq l2) : ls1(l1), ls2(l2) {} +}; + +double intersect(const ray &r, const line &l); +double nextintersect(const ray &r, const lineseq &ls); +bool nextcell(ray &r, const grid &g, bool pass_corner); + +} + +#endif + diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj index 3d6c68b246..0bf8af4fa2 100644 --- a/crawl-ref/source/makefile.obj +++ b/crawl-ref/source/makefile.obj @@ -33,6 +33,7 @@ fight.o \ files.o \ food.o \ format.o \ +geom2d.o \ ghost.o \ godabil.o \ goditem.o \ -- cgit v1.2.3-54-g00ecf