src/shared/geom.h

   1
   2 struct vec
   3 {
   4     union
   5     {
   6         struct { float x, y, z; };
   7         float v[3];
   8     };
   9
  10     vec() {}
  11     vec(int a) : x(a), y(a), z(a) {}
  12     vec(float a) : x(a), y(a), z(a) {}
  13     vec(float a, float b, float c) : x(a), y(b), z(c) {}
  14     vec(int v[3]) : x(v[0]), y(v[1]), z(v[2]) {}
  15     vec(float *v) : x(v[0]), y(v[1]), z(v[2]) {}
  16
  17     vec(float yaw, float pitch) : x(sinf(yaw)*cosf(pitch)), y(-cosf(yaw)*cosf(pitch)), z(sinf(pitch)) {}
  18
  19     float &operator[](int i)       { return v[i]; }
  20     float  operator[](int i) const { return v[i]; }
  21
  22     vec &set(int i, float f) { v[i] = f; return *this; }
  23
  24     bool operator==(const vec &o) const { return x == o.x && y == o.y && z == o.z; }
  25     bool operator!=(const vec &o) const { return x != o.x || y != o.y || z != o.z; }
  26
  27     bool iszero() const { return x==0 && y==0 && z==0; }
  28     float squaredlen() const { return x*x + y*y + z*z; }
  29     float dot(const vec &o) const { return x*o.x + y*o.y + z*o.z; }
  30     vec &mul(float f)        { x *= f; y *= f; z *= f; return *this; }
  31     vec &div(float f)        { x /= f; y /= f; z /= f; return *this; }
  32     vec &add(const vec &o)   { x += o.x; y += o.y; z += o.z; return *this; }
  33     vec &add(float f)        { x += f; y += f; z += f; return *this; }
  34     vec &sub(const vec &o)   { x -= o.x; y -= o.y; z -= o.z; return *this; }
  35     vec &sub(float f)        { x -= f; y -= f; z -= f; return *this; }
  36     vec &neg()               { return mul(-1); }
  37     float magnitude() const  { return sqrtf(squaredlen()); }
  38     vec &normalize()         { div(magnitude()); return *this; }
  39     bool isnormalized() const { float m = squaredlen(); return (m>0.99f && m<1.01f); }
  40     float dist(const vec &e) const { vec t; return dist(e, t); }
  41     float dist(const vec &e, vec &t) const { t = *this; t.sub(e); return t.magnitude(); }
  42     bool reject(const vec &o, float max) { return x>o.x+max || x<o.x-max || y>o.y+max || y<o.y-max; }
  43     vec &cross(const vec &a, const vec &b) { x = a.y*b.z-a.z*b.y; y = a.z*b.x-a.x*b.z; z = a.x*b.y-a.y*b.x; return *this; }
  44
  45     void rotate_around_z(float angle) { *this = vec(cosf(angle)*x-sinf(angle)*y, cosf(angle)*y+sinf(angle)*x, z); }
  46     void rotate_around_x(float angle) { *this = vec(x, cosf(angle)*y-sinf(angle)*z, cosf(angle)*z+sinf(angle)*y); }
  47     void rotate_around_y(float angle) { *this = vec(cosf(angle)*x-sinf(angle)*z, y, cosf(angle)*z+sinf(angle)*x); }
  48
  49     void rotate(float angle, const vec &d)
  50     {
  51         float c = cosf(angle), s = sinf(angle);
  52         rotate(c, s, d);
  53     }
  54
  55     void rotate(float c, float s, const vec &d)
  56     {
  57         *this = vec(x*(d.x*d.x*(1-c)+c) + y*(d.x*d.y*(1-c)-d.z*s) + z*(d.x*d.z*(1-c)+d.y*s),
  58                     x*(d.y*d.x*(1-c)+d.z*s) + y*(d.y*d.y*(1-c)+c) + z*(d.y*d.z*(1-c)-d.x*s),
  59                     x*(d.x*d.z*(1-c)-d.y*s) + y*(d.y*d.z*(1-c)+d.x*s) + z*(d.z*d.z*(1-c)+c));
  60     }
  61
  62     void orthogonal(const vec &d)
  63     {
  64         int i = fabs(d.x) > fabs(d.y) ? (fabs(d.x) > fabs(d.z) ? 0 : 2) : (fabs(d.y) > fabs(d.z) ? 1 : 2);
  65         v[i] = d[(i+1)%3];
  66         v[(i+1)%3] = -d[i];
  67         v[(i+2)%3] = 0;
  68     }
  69
  70     template<class T> float dist_to_bb(const T &min, const T &max) const
  71     {
  72         float sqrdist = 0;
  73         loopi(3)
  74         {
  75             if     (v[i] < min[i]) { float delta = v[i]-min[i]; sqrdist += delta*delta; }
  76             else if(v[i] > max[i]) { float delta = max[i]-v[i]; sqrdist += delta*delta; }
  77         }
  78         return sqrtf(sqrdist);
  79     }
  80
  81     template<class T, class S> float dist_to_bb(const T &o, S size) const
  82     {
  83         return dist_to_bb(o, T(o).add(size));
  84     }
  85 };
  86
  87 struct vec4 : vec
  88 {
  89     float w;
  90     vec4() : w(0) {}
  91     vec4(vec &_v, float _w = 0) : w(_w) { *(vec *)this = _v; }
  92 };
  93
  94 struct matrix
  95 {
  96     vec X, Y, Z;
  97
  98     matrix() {}
  99     matrix(const vec &x, const vec &y, const vec &z) : X(x), Y(y), Z(z) {}
 100
 101     void transform(vec &o) { o = vec(o.dot(X), o.dot(Y), o.dot(Z)); }
 102
 103     void orthonormalize()
 104     {
 105         X.sub(vec(Z).mul(Z.dot(X)));
 106         Y.sub(vec(Z).mul(Z.dot(Y)))
 107          .sub(vec(X).mul(X.dot(Y)));
 108     }
 109
 110     void rotate(float angle, const vec &d)
 111     {
 112         float c = cosf(angle), s = sinf(angle);
 113         rotate(c, s, d);
 114     }
 115
 116     void rotate(float c, float s, const vec &d)
 117     {
 118         X = vec(d.x*d.x*(1-c)+c, d.x*d.y*(1-c)-d.z*s, d.x*d.z*(1-c)+d.y*s);
 119         Y = vec(d.y*d.x*(1-c)+d.z*s, d.y*d.y*(1-c)+c, d.y*d.z*(1-c)-d.x*s);
 120         Z = vec(d.x*d.z*(1-c)-d.y*s, d.y*d.z*(1-c)+d.x*s, d.z*d.z*(1-c)+c);
 121     }
 122
 123     void transposedtransform(vec &d)
 124     {
 125         d = vec(X.x*d.x + Y.x*d.y + Z.x*d.z,
 126                 X.y*d.x + Y.y*d.y + Z.y*d.z,
 127                 X.z*d.x + Y.z*d.y + Z.z*d.z);
 128     }
 129 };
 130
 131 struct plane : vec
 132 {
 133     float offset;
 134
 135     float dist(const vec &p) const { return dot(p)+offset; }
 136     bool operator==(const plane &p) const { return x==p.x && y==p.y && z==p.z && offset==p.offset; }
 137     bool operator!=(const plane &p) const { return x!=p.x || y!=p.y || z!=p.z || offset!=p.offset; }
 138
 139     plane() {}
 140     plane(vec &c, float off) : vec(c), offset(off) {}
 141     plane(int d, float off)
 142     {
 143         x = y = z = 0.0f;
 144         v[d] = 1.0f;
 145         offset = -off;
 146     }
 147     plane(float a, float b, float c, float d) : vec(a, b, c), offset(d) {}
 148
 149     void toplane(const vec &n, const vec &p)
 150     {
 151         x = n.x; y = n.y; z = n.z;
 152         offset = -dot(p);
 153     }
 154
 155     bool toplane(const vec &a, const vec &b, const vec &c)
 156     {
 157         cross(vec(b).sub(a), vec(c).sub(a));
 158         float mag = magnitude();
 159         if(!mag) return false;
 160         div(mag);
 161         offset = -dot(a);
 162         return true;
 163     }
 164
 165     bool rayintersect(const vec &o, const vec &ray, float &dist)
 166     {
 167         float cosalpha = dot(ray);
 168         if(cosalpha==0) return false;
 169         float deltac = offset+dot(o);
 170         dist -= deltac/cosalpha;
 171         return true;
 172     }
 173
 174     float zintersect(const vec &p) const { return -(x*p.x+y*p.y+offset)/z; }
 175     float zdist(const vec &p) const { return p.z-zintersect(p); }
 176 };
 177
 178 struct triangle
 179 {
 180     vec a, b, c;
 181
 182     triangle(const vec &a, const vec &b, const vec &c) : a(a), b(b), c(c) {}
 183     triangle() {}
 184
 185     triangle &add(const vec &o) { a.add(o); b.add(o); c.add(o); return *this; }
 186     triangle &sub(const vec &o) { a.sub(o); b.sub(o); c.sub(o); return *this; }
 187
 188     bool operator==(const triangle &t) const { return a == t.a && b == t.b && c == t.c; }
 189 };
 190
 191 /**
 192
 193 Sauerbraten uses 3 different linear coordinate systems
 194 which are oriented around each of the axis dimensions.
 195
 196 So any point within the game can be defined by four coordinates: (d, x, y, z)
 197
 198 d is the reference axis dimension
 199 x is the coordinate of the ROW dimension
 200 y is the coordinate of the COL dimension
 201 z is the coordinate of the reference dimension (DEPTH)
 202
 203 typically, if d is not used, then it is implicitly the Z dimension.
 204 ie: d=z => x=x, y=y, z=z
 205
 206 **/
 207
 208 // DIM: X=0 Y=1 Z=2.
 209 const int R[3]  = {1, 2, 0}; // row
 210 const int C[3]  = {2, 0, 1}; // col
 211 const int D[3]  = {0, 1, 2}; // depth
 212
 213 struct ivec
 214 {
 215     union
 216     {
 217         struct { int x, y, z; };
 218         int v[3];
 219     };
 220
 221     ivec() {}
 222     ivec(const vec &v) : x(int(v.x)), y(int(v.y)), z(int(v.z)) {}
 223     ivec(int i)
 224     {
 225         x = ((i&1)>>0);
 226         y = ((i&2)>>1);
 227         z = ((i&4)>>2);
 228     }
 229     ivec(int a, int b, int c) : x(a), y(b), z(c) {}
 230     ivec(int d, int row, int col, int depth)
 231     {
 232         v[R[d]] = row;
 233         v[C[d]] = col;
 234         v[D[d]] = depth;
 235     }
 236     ivec(int i, int cx, int cy, int cz, int size)
 237     {
 238         x = cx+((i&1)>>0)*size;
 239         y = cy+((i&2)>>1)*size;
 240         z = cz+((i&4)>>2)*size;
 241     }
 242     vec tovec() const { return vec(x, y, z); }
 243     int toint() const { return (x>0?1:0) + (y>0?2:0) + (z>0?4:0); }
 244
 245     int &operator[](int i)       { return v[i]; }
 246     int  operator[](int i) const { return v[i]; }
 247
 248     //int idx(int i) { return v[i]; }
 249     bool operator==(const ivec &v) const { return x==v.x && y==v.y && z==v.z; }
 250     bool operator!=(const ivec &v) const { return x!=v.x || y!=v.y || z!=v.z; }
 251     ivec &shl(int n) { x<<= n; y<<= n; z<<= n; return *this; }
 252     ivec &shr(int n) { x>>= n; y>>= n; z>>= n; return *this; }
 253     ivec &mul(int n) { x *= n; y *= n; z *= n; return *this; }
 254     ivec &div(int n) { x /= n; y /= n; z /= n; return *this; }
 255     ivec &add(int n) { x += n; y += n; z += n; return *this; }
 256     ivec &sub(int n) { x -= n; y -= n; z -= n; return *this; }
 257     ivec &add(const ivec &v) { x += v.x; y += v.y; z += v.z; return *this; }
 258     ivec &sub(const ivec &v) { x -= v.x; y -= v.y; z -= v.z; return *this; }
 259     ivec &mask(int n) { x &= n; y &= n; z &= n; return *this; }
 260     ivec &cross(const ivec &a, const ivec &b) { x = a.y*b.z-a.z*b.y; y = a.z*b.x-a.x*b.z; z = a.x*b.y-a.y*b.x; return *this; }
 261     int dot(const ivec &o) const { return x*o.x + y*o.y + z*o.z; }
 262 };
 263
 264 static inline bool htcmp(const ivec &x, const ivec &y)
 265 {
 266     return x == y;
 267 }
 268
 269 static inline uint hthash(const ivec &k)
 270 {
 271     return k.x^k.y^k.z;
 272 }
 273
 274 struct svec
 275 {
 276     union
 277     {
 278         struct { short x, y, z; };
 279         short v[3];
 280     };
 281
 282     svec() {}
 283     svec(short x, short y, short z) : x(x), y(y), z(z) {}
 284
 285     short &operator[](int i)       { return v[i]; }
 286     short  operator[](int i) const { return v[i]; }
 287
 288     bool operator==(const svec &v) const { return x==v.x && y==v.y && z==v.z; }
 289     bool operator!=(const svec &v) const { return x!=v.x || y!=v.y || z!=v.z; }
 290
 291     void add(const svec &o) { x += o.x; y += o.y; z += o.z; }
 292     void sub(const svec &o) { x -= o.x; y -= o.y; z -= o.z; }
 293     void mul(int f) { x *= f; y *= f; z *= f; }
 294     void div(int f) { x /= f; y /= f; z /= f; }
 295
 296     bool iszero() const { return x==0 && y==0 && z==0; }
 297 };
 298
 299 struct bvec
 300 {
 301     union
 302     {
 303         struct { uchar x, y, z; };
 304         uchar v[3];
 305     };
 306
 307     bvec() {}
 308     bvec(uchar x, uchar y, uchar z) : x(x), y(y), z(z) {}
 309     bvec(const vec &v) : x((uchar)((v.x+1)*255/2)), y((uchar)((v.y+1)*255/2)), z((uchar)((v.z+1)*255/2)) {}
 310
 311     uchar &operator[](int i)       { return v[i]; }
 312     uchar  operator[](int i) const { return v[i]; }
 313
 314     bool operator==(const bvec &v) const { return x==v.x && y==v.y && z==v.z; }
 315     bool operator!=(const bvec &v) const { return x!=v.x || y!=v.y || z!=v.z; }
 316
 317     bool iszero() const { return x==0 && y==0 && z==0; }
 318
 319     vec tovec() const { return vec(x*(2.0f/255.0f)-1.0f, y*(2.0f/255.0f)-1.0f, z*(2.0f/255.0f)-1.0f); }
 320 };
 321
 322 extern bool raysphereintersect(vec c, float radius, const vec &o, const vec &ray, float &dist);
 323 extern bool rayrectintersect(const vec &b, const vec &s, const vec &o, const vec &ray, float &dist, int &orient);
 324
 325 enum { INTERSECT_NONE, INTERSECT_OVERLAP, INTERSECT_BEFORESTART, INTERSECT_MIDDLE, INTERSECT_AFTEREND };
 326 extern int intersect_plane_line(vec &linestart, vec &linestop, vec &planeorig, vec &planenormal, vec &intersectionpoint);
 327