2 * ICE / OPCODE - Optimized Collision Detection
3 * http://www.codercorner.com/Opcode.htm
5 * Copyright (c) 2001-2008 Pierre Terdiman, pierre@codercorner.com
7 This software is provided 'as-is', without any express or implied warranty.
8 In no event will the authors be held liable for any damages arising from the use of this software.
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it freely,
11 subject to the following restrictions:
13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
15 3. This notice may not be removed or altered from any source distribution.
17 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19 * Contains code for 3D vectors.
21 * \author Pierre Terdiman
22 * \date April, 4, 2000
24 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
26 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
28 #ifndef __ICEPOINT_H__
29 #define __ICEPOINT_H__
31 // Forward declarations
37 #define CROSS2D(a, b) (a.x*b.y - b.x*a.y)
39 const float EPSILON2 = 1.0e-20f;
41 class ICEMATHS_API Point
47 //! Constructor from a single float
48 // inline_ Point(float val) : x(val), y(val), z(val) {}
49 // Removed since it introduced the nasty "Point T = *Matrix4x4.GetTrans();" bug.......
50 //! Constructor from floats
51 inline_ Point(float _x, float _y, float _z) : x(_x), y(_y), z(_z) {}
52 //! Constructor from array
53 inline_ Point(const float f[3]) : x(f[_X]), y(f[_Y]), z(f[_Z]) {}
55 inline_ Point(const Point& p) : x(p.x), y(p.y), z(p.z) {}
60 inline_ Point& Zero() { x = y = z = 0.0f; return *this; }
63 inline_ Point& SetPlusInfinity() { x = y = z = MAX_FLOAT; return *this; }
65 inline_ Point& SetMinusInfinity() { x = y = z = MIN_FLOAT; return *this; }
67 //! Sets positive unit random vector
68 Point& PositiveUnitRandomVector();
69 //! Sets unit random vector
70 Point& UnitRandomVector();
72 //! Assignment from values
73 inline_ Point& Set(float _x, float _y, float _z) { x = _x; y = _y; z = _z; return *this; }
74 //! Assignment from array
75 inline_ Point& Set(const float f[3]) { x = f[_X]; y = f[_Y]; z = f[_Z]; return *this; }
76 //! Assignment from another point
77 inline_ Point& Set(const Point& src) { x = src.x; y = src.y; z = src.z; return *this; }
80 inline_ Point& Add(const Point& p) { x += p.x; y += p.y; z += p.z; return *this; }
82 inline_ Point& Add(float _x, float _y, float _z) { x += _x; y += _y; z += _z; return *this; }
84 inline_ Point& Add(const float f[3]) { x += f[_X]; y += f[_Y]; z += f[_Z]; return *this; }
86 inline_ Point& Add(const Point& p, const Point& q) { x = p.x+q.x; y = p.y+q.y; z = p.z+q.z; return *this; }
88 //! Subtracts a vector
89 inline_ Point& Sub(const Point& p) { x -= p.x; y -= p.y; z -= p.z; return *this; }
90 //! Subtracts a vector
91 inline_ Point& Sub(float _x, float _y, float _z) { x -= _x; y -= _y; z -= _z; return *this; }
92 //! Subtracts a vector
93 inline_ Point& Sub(const float f[3]) { x -= f[_X]; y -= f[_Y]; z -= f[_Z]; return *this; }
95 inline_ Point& Sub(const Point& p, const Point& q) { x = p.x-q.x; y = p.y-q.y; z = p.z-q.z; return *this; }
98 inline_ Point& Neg() { x = -x; y = -y; z = -z; return *this; }
100 inline_ Point& Neg(const Point& a) { x = -a.x; y = -a.y; z = -a.z; return *this; }
102 //! Multiplies by a scalar
103 inline_ Point& Mult(float s) { x *= s; y *= s; z *= s; return *this; }
105 //! this = a * scalar
106 inline_ Point& Mult(const Point& a, float scalar)
114 //! this = a + b * scalar
115 inline_ Point& Mac(const Point& a, const Point& b, float scalar)
117 x = a.x + b.x * scalar;
118 y = a.y + b.y * scalar;
119 z = a.z + b.z * scalar;
123 //! this = this + a * scalar
124 inline_ Point& Mac(const Point& a, float scalar)
132 //! this = a - b * scalar
133 inline_ Point& Msc(const Point& a, const Point& b, float scalar)
135 x = a.x - b.x * scalar;
136 y = a.y - b.y * scalar;
137 z = a.z - b.z * scalar;
141 //! this = this - a * scalar
142 inline_ Point& Msc(const Point& a, float scalar)
150 //! this = a + b * scalarb + c * scalarc
151 inline_ Point& Mac2(const Point& a, const Point& b, float scalarb, const Point& c, float scalarc)
153 x = a.x + b.x * scalarb + c.x * scalarc;
154 y = a.y + b.y * scalarb + c.y * scalarc;
155 z = a.z + b.z * scalarb + c.z * scalarc;
159 //! this = a - b * scalarb - c * scalarc
160 inline_ Point& Msc2(const Point& a, const Point& b, float scalarb, const Point& c, float scalarc)
162 x = a.x - b.x * scalarb - c.x * scalarc;
163 y = a.y - b.y * scalarb - c.y * scalarc;
164 z = a.z - b.z * scalarb - c.z * scalarc;
169 inline_ Point& Mult(const Matrix3x3& mat, const Point& a);
171 //! this = mat1 * a1 + mat2 * a2
172 inline_ Point& Mult2(const Matrix3x3& mat1, const Point& a1, const Matrix3x3& mat2, const Point& a2);
174 //! this = this + mat * a
175 inline_ Point& Mac(const Matrix3x3& mat, const Point& a);
177 //! this = transpose(mat) * a
178 inline_ Point& TransMult(const Matrix3x3& mat, const Point& a);
180 //! Linear interpolate between two vectors: this = a + t * (b - a)
181 inline_ Point& Lerp(const Point& a, const Point& b, float t)
183 x = a.x + t * (b.x - a.x);
184 y = a.y + t * (b.y - a.y);
185 z = a.z + t * (b.z - a.z);
189 //! Hermite interpolate between p1 and p2. p0 and p3 are used for finding gradient at p1 and p2.
190 //! this = p0 * (2t^2 - t^3 - t)/2
191 //! + p1 * (3t^3 - 5t^2 + 2)/2
192 //! + p2 * (4t^2 - 3t^3 + t)/2
193 //! + p3 * (t^3 - t^2)/2
194 inline_ Point& Herp(const Point& p0, const Point& p1, const Point& p2, const Point& p3, float t)
198 float kp0 = (2.0f * t2 - t3 - t) * 0.5f;
199 float kp1 = (3.0f * t3 - 5.0f * t2 + 2.0f) * 0.5f;
200 float kp2 = (4.0f * t2 - 3.0f * t3 + t) * 0.5f;
201 float kp3 = (t3 - t2) * 0.5f;
202 x = p0.x * kp0 + p1.x * kp1 + p2.x * kp2 + p3.x * kp3;
203 y = p0.y * kp0 + p1.y * kp1 + p2.y * kp2 + p3.y * kp3;
204 z = p0.z * kp0 + p1.z * kp1 + p2.z * kp2 + p3.z * kp3;
208 //! this = rotpos * r + linpos
209 inline_ Point& Transform(const Point& r, const Matrix3x3& rotpos, const Point& linpos);
211 //! this = trans(rotpos) * (r - linpos)
212 inline_ Point& InvTransform(const Point& r, const Matrix3x3& rotpos, const Point& linpos);
214 //! Returns MIN(x, y, z);
215 inline_ float Min() const { return MIN(x, MIN(y, z)); }
216 //! Returns MAX(x, y, z);
217 inline_ float Max() const { return MAX(x, MAX(y, z)); }
218 //! Sets each element to be componentwise minimum
219 inline_ Point& Min(const Point& p) { x = MIN(x, p.x); y = MIN(y, p.y); z = MIN(z, p.z); return *this; }
220 //! Sets each element to be componentwise maximum
221 inline_ Point& Max(const Point& p) { x = MAX(x, p.x); y = MAX(y, p.y); z = MAX(z, p.z); return *this; }
223 //! Clamps each element
224 inline_ Point& Clamp(float min, float max)
226 if(x<min) x=min; if(x>max) x=max;
227 if(y<min) y=min; if(y>max) y=max;
228 if(z<min) z=min; if(z>max) z=max;
232 //! Computes square magnitude
233 inline_ float SquareMagnitude() const { return x*x + y*y + z*z; }
234 //! Computes magnitude
235 inline_ float Magnitude() const { return sqrtf(x*x + y*y + z*z); }
237 inline_ float Volume() const { return x * y * z; }
239 //! Checks the point is near zero
240 inline_ bool ApproxZero() const { return SquareMagnitude() < EPSILON2; }
242 //! Tests for exact zero vector
243 inline_ BOOL IsZero() const
245 if(IR(x) || IR(y) || IR(z)) return FALSE;
249 //! Checks point validity
250 inline_ BOOL IsValid() const
252 if(!IsValidFloat(x)) return FALSE;
253 if(!IsValidFloat(y)) return FALSE;
254 if(!IsValidFloat(z)) return FALSE;
258 //! Slighty moves the point
259 void Tweak(udword coord_mask, udword tweak_mask)
261 if(coord_mask&1) { udword Dummy = IR(x); Dummy^=tweak_mask; x = FR(Dummy); }
262 if(coord_mask&2) { udword Dummy = IR(y); Dummy^=tweak_mask; y = FR(Dummy); }
263 if(coord_mask&4) { udword Dummy = IR(z); Dummy^=tweak_mask; z = FR(Dummy); }
266 #define TWEAKMASK 0x3fffff
267 #define TWEAKNOTMASK ~TWEAKMASK
268 //! Slighty moves the point out
269 inline_ void TweakBigger()
271 udword Dummy = (IR(x)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(x)) Dummy+=TWEAKMASK+1; x = FR(Dummy);
272 Dummy = (IR(y)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(y)) Dummy+=TWEAKMASK+1; y = FR(Dummy);
273 Dummy = (IR(z)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(z)) Dummy+=TWEAKMASK+1; z = FR(Dummy);
276 //! Slighty moves the point in
277 inline_ void TweakSmaller()
279 udword Dummy = (IR(x)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(x)) Dummy+=TWEAKMASK+1; x = FR(Dummy);
280 Dummy = (IR(y)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(y)) Dummy+=TWEAKMASK+1; y = FR(Dummy);
281 Dummy = (IR(z)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(z)) Dummy+=TWEAKMASK+1; z = FR(Dummy);
284 //! Normalizes the vector
285 inline_ Point& Normalize()
287 float M = x*x + y*y + z*z;
298 //! Sets vector length
299 inline_ Point& SetLength(float length)
301 float NewLength = length / Magnitude();
308 //! Clamps vector length
309 inline_ Point& ClampLength(float limit_length)
311 if(limit_length>=0.0f) // Magnitude must be positive
313 float CurrentSquareLength = SquareMagnitude();
315 if(CurrentSquareLength > limit_length * limit_length)
317 float Coeff = limit_length / sqrtf(CurrentSquareLength);
326 //! Computes distance to another point
327 inline_ float Distance(const Point& b) const
329 return sqrtf((x - b.x)*(x - b.x) + (y - b.y)*(y - b.y) + (z - b.z)*(z - b.z));
332 //! Computes square distance to another point
333 inline_ float SquareDistance(const Point& b) const
335 return ((x - b.x)*(x - b.x) + (y - b.y)*(y - b.y) + (z - b.z)*(z - b.z));
338 //! Dot product dp = this|a
339 inline_ float Dot(const Point& p) const { return p.x * x + p.y * y + p.z * z; }
341 //! Cross product this = a x b
342 inline_ Point& Cross(const Point& a, const Point& b)
344 x = a.y * b.z - a.z * b.y;
345 y = a.z * b.x - a.x * b.z;
346 z = a.x * b.y - a.y * b.x;
350 //! Vector code ( bitmask = sign(z) | sign(y) | sign(x) )
351 inline_ udword VectorCode() const
353 return (IR(x)>>31) | ((IR(y)&SIGN_BITMASK)>>30) | ((IR(z)&SIGN_BITMASK)>>29);
356 //! Returns largest axis
357 inline_ PointComponent LargestAxis() const
359 const float* Vals = &x;
360 PointComponent m = _X;
361 if(Vals[_Y] > Vals[m]) m = _Y;
362 if(Vals[_Z] > Vals[m]) m = _Z;
366 //! Returns closest axis
367 inline_ PointComponent ClosestAxis() const
369 const float* Vals = &x;
370 PointComponent m = _X;
371 if(AIR(Vals[_Y]) > AIR(Vals[m])) m = _Y;
372 if(AIR(Vals[_Z]) > AIR(Vals[m])) m = _Z;
376 //! Returns smallest axis
377 inline_ PointComponent SmallestAxis() const
379 const float* Vals = &x;
380 PointComponent m = _X;
381 if(Vals[_Y] < Vals[m]) m = _Y;
382 if(Vals[_Z] < Vals[m]) m = _Z;
386 //! Refracts the point
387 Point& Refract(const Point& eye, const Point& n, float refractindex, Point& refracted);
389 //! Projects the point onto a plane
390 Point& ProjectToPlane(const Plane& p);
392 //! Projects the point onto the screen
393 void ProjectToScreen(float halfrenderwidth, float halfrenderheight, const Matrix4x4& mat, HPoint& projected) const;
395 //! Unfolds the point onto a plane according to edge(a,b)
396 Point& Unfold(Plane& p, Point& a, Point& b);
398 //! Hash function from Ville Miettinen
399 inline_ udword GetHashValue() const
401 const udword* h = (const udword*)(this);
402 udword f = (h[0]+h[1]*11-(h[2]*17)) & 0x7fffffff; // avoid problems with +-0
403 return (f>>22)^(f>>12)^(f);
406 //! Stuff magic values in the point, marking it as explicitely not used.
408 //! Checks the point is marked as not used
409 BOOL IsNotUsed() const;
411 // Arithmetic operators
413 //! Unary operator for Point Negate = - Point
414 inline_ Point operator-() const { return Point(-x, -y, -z); }
416 //! Operator for Point Plus = Point + Point.
417 inline_ Point operator+(const Point& p) const { return Point(x + p.x, y + p.y, z + p.z); }
418 //! Operator for Point Minus = Point - Point.
419 inline_ Point operator-(const Point& p) const { return Point(x - p.x, y - p.y, z - p.z); }
421 //! Operator for Point Mul = Point * Point.
422 inline_ Point operator*(const Point& p) const { return Point(x * p.x, y * p.y, z * p.z); }
423 //! Operator for Point Scale = Point * float.
424 inline_ Point operator*(float s) const { return Point(x * s, y * s, z * s ); }
425 //! Operator for Point Scale = float * Point.
426 inline_ friend Point operator*(float s, const Point& p) { return Point(s * p.x, s * p.y, s * p.z); }
428 //! Operator for Point Div = Point / Point.
429 inline_ Point operator/(const Point& p) const { return Point(x / p.x, y / p.y, z / p.z); }
430 //! Operator for Point Scale = Point / float.
431 inline_ Point operator/(float s) const { s = 1.0f / s; return Point(x * s, y * s, z * s); }
432 //! Operator for Point Scale = float / Point.
433 inline_ friend Point operator/(float s, const Point& p) { return Point(s / p.x, s / p.y, s / p.z); }
435 //! Operator for float DotProd = Point | Point.
436 inline_ float operator|(const Point& p) const { return x*p.x + y*p.y + z*p.z; }
437 //! Operator for Point VecProd = Point ^ Point.
438 inline_ Point operator^(const Point& p) const
446 //! Operator for Point += Point.
447 inline_ Point& operator+=(const Point& p) { x += p.x; y += p.y; z += p.z; return *this; }
448 //! Operator for Point += float.
449 inline_ Point& operator+=(float s) { x += s; y += s; z += s; return *this; }
451 //! Operator for Point -= Point.
452 inline_ Point& operator-=(const Point& p) { x -= p.x; y -= p.y; z -= p.z; return *this; }
453 //! Operator for Point -= float.
454 inline_ Point& operator-=(float s) { x -= s; y -= s; z -= s; return *this; }
456 //! Operator for Point *= Point.
457 inline_ Point& operator*=(const Point& p) { x *= p.x; y *= p.y; z *= p.z; return *this; }
458 //! Operator for Point *= float.
459 inline_ Point& operator*=(float s) { x *= s; y *= s; z *= s; return *this; }
461 //! Operator for Point /= Point.
462 inline_ Point& operator/=(const Point& p) { x /= p.x; y /= p.y; z /= p.z; return *this; }
463 //! Operator for Point /= float.
464 inline_ Point& operator/=(float s) { s = 1.0f/s; x *= s; y *= s; z *= s; return *this; }
468 //! Operator for "if(Point==Point)"
469 inline_ bool operator==(const Point& p) const { return ( (IR(x)==IR(p.x))&&(IR(y)==IR(p.y))&&(IR(z)==IR(p.z))); }
470 //! Operator for "if(Point!=Point)"
471 inline_ bool operator!=(const Point& p) const { return ( (IR(x)!=IR(p.x))||(IR(y)!=IR(p.y))||(IR(z)!=IR(p.z))); }
473 // Arithmetic operators
475 //! Operator for Point Mul = Point * Matrix3x3.
476 inline_ Point operator*(const Matrix3x3& mat) const
478 class ShadowMatrix3x3{ public: float m[3][3]; }; // To allow inlining
479 const ShadowMatrix3x3* Mat = (const ShadowMatrix3x3*)&mat;
482 x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0],
483 x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1],
484 x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] );
487 //! Operator for Point Mul = Point * Matrix4x4.
488 inline_ Point operator*(const Matrix4x4& mat) const
490 class ShadowMatrix4x4{ public: float m[4][4]; }; // To allow inlining
491 const ShadowMatrix4x4* Mat = (const ShadowMatrix4x4*)&mat;
494 x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0] + Mat->m[3][0],
495 x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1] + Mat->m[3][1],
496 x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] + Mat->m[3][2]);
499 //! Operator for Point *= Matrix3x3.
500 inline_ Point& operator*=(const Matrix3x3& mat)
502 class ShadowMatrix3x3{ public: float m[3][3]; }; // To allow inlining
503 const ShadowMatrix3x3* Mat = (const ShadowMatrix3x3*)&mat;
505 float xp = x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0];
506 float yp = x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1];
507 float zp = x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2];
509 x = xp; y = yp; z = zp;
514 //! Operator for Point *= Matrix4x4.
515 inline_ Point& operator*=(const Matrix4x4& mat)
517 class ShadowMatrix4x4{ public: float m[4][4]; }; // To allow inlining
518 const ShadowMatrix4x4* Mat = (const ShadowMatrix4x4*)&mat;
520 float xp = x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0] + Mat->m[3][0];
521 float yp = x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1] + Mat->m[3][1];
522 float zp = x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] + Mat->m[3][2];
524 x = xp; y = yp; z = zp;
531 //! Cast a Point to a HPoint. w is set to zero.
532 operator HPoint() const;
534 inline_ operator const float*() const { return &x; }
535 inline_ operator float*() { return &x; }
541 FUNCTION ICEMATHS_API void Normalize1(Point& a);
542 FUNCTION ICEMATHS_API void Normalize2(Point& a);
544 #endif //__ICEPOINT_H__