From e33e19d0587146859d48a134ec9fd94e7b7ba5cd Mon Sep 17 00:00:00 2001 From: "FWoltermann@gmail.com" Date: Thu, 8 Dec 2011 14:53:40 +0000 Subject: Initial upload --- Opcode/Ice/IceAABB.cpp | 405 ++++++++++++++++++++++++++++ Opcode/Ice/IceAABB.h | 505 +++++++++++++++++++++++++++++++++++ Opcode/Ice/IceAxes.h | 54 ++++ Opcode/Ice/IceBoundingSphere.h | 142 ++++++++++ Opcode/Ice/IceContainer.cpp | 345 ++++++++++++++++++++++++ Opcode/Ice/IceContainer.h | 212 +++++++++++++++ Opcode/Ice/IceFPU.h | 317 ++++++++++++++++++++++ Opcode/Ice/IceHPoint.cpp | 70 +++++ Opcode/Ice/IceHPoint.h | 157 +++++++++++ Opcode/Ice/IceIndexedTriangle.cpp | 548 ++++++++++++++++++++++++++++++++++++++ Opcode/Ice/IceIndexedTriangle.h | 68 +++++ Opcode/Ice/IceLSS.h | 75 ++++++ Opcode/Ice/IceMatrix3x3.cpp | 48 ++++ Opcode/Ice/IceMatrix3x3.h | 496 ++++++++++++++++++++++++++++++++++ Opcode/Ice/IceMatrix4x4.cpp | 135 ++++++++++ Opcode/Ice/IceMatrix4x4.h | 455 +++++++++++++++++++++++++++++++ Opcode/Ice/IceMemoryMacros.h | 105 ++++++++ Opcode/Ice/IceOBB.cpp | 323 ++++++++++++++++++++++ Opcode/Ice/IceOBB.h | 177 ++++++++++++ Opcode/Ice/IcePairs.h | 45 ++++ Opcode/Ice/IcePlane.cpp | 45 ++++ Opcode/Ice/IcePlane.h | 113 ++++++++ Opcode/Ice/IcePoint.cpp | 193 ++++++++++++++ Opcode/Ice/IcePoint.h | 528 ++++++++++++++++++++++++++++++++++++ Opcode/Ice/IcePreprocessor.h | 128 +++++++++ Opcode/Ice/IceRandom.cpp | 35 +++ Opcode/Ice/IceRandom.h | 42 +++ Opcode/Ice/IceRay.cpp | 84 ++++++ Opcode/Ice/IceRay.h | 98 +++++++ Opcode/Ice/IceRevisitedRadix.cpp | 520 ++++++++++++++++++++++++++++++++++++ Opcode/Ice/IceRevisitedRadix.h | 65 +++++ Opcode/Ice/IceSegment.cpp | 57 ++++ Opcode/Ice/IceSegment.h | 55 ++++ Opcode/Ice/IceTriangle.cpp | 286 ++++++++++++++++++++ Opcode/Ice/IceTriangle.h | 68 +++++ Opcode/Ice/IceTrilist.h | 61 +++++ Opcode/Ice/IceTypes.h | 157 +++++++++++ Opcode/Ice/IceUtils.cpp | 39 +++ Opcode/Ice/IceUtils.h | 256 ++++++++++++++++++ 39 files changed, 7512 insertions(+) create mode 100644 Opcode/Ice/IceAABB.cpp create mode 100644 Opcode/Ice/IceAABB.h create mode 100644 Opcode/Ice/IceAxes.h create mode 100644 Opcode/Ice/IceBoundingSphere.h create mode 100644 Opcode/Ice/IceContainer.cpp create mode 100644 Opcode/Ice/IceContainer.h create mode 100644 Opcode/Ice/IceFPU.h create mode 100644 Opcode/Ice/IceHPoint.cpp create mode 100644 Opcode/Ice/IceHPoint.h create mode 100644 Opcode/Ice/IceIndexedTriangle.cpp create mode 100644 Opcode/Ice/IceIndexedTriangle.h create mode 100644 Opcode/Ice/IceLSS.h create mode 100644 Opcode/Ice/IceMatrix3x3.cpp create mode 100644 Opcode/Ice/IceMatrix3x3.h create mode 100644 Opcode/Ice/IceMatrix4x4.cpp create mode 100644 Opcode/Ice/IceMatrix4x4.h create mode 100644 Opcode/Ice/IceMemoryMacros.h create mode 100644 Opcode/Ice/IceOBB.cpp create mode 100644 Opcode/Ice/IceOBB.h create mode 100644 Opcode/Ice/IcePairs.h create mode 100644 Opcode/Ice/IcePlane.cpp create mode 100644 Opcode/Ice/IcePlane.h create mode 100644 Opcode/Ice/IcePoint.cpp create mode 100644 Opcode/Ice/IcePoint.h create mode 100644 Opcode/Ice/IcePreprocessor.h create mode 100644 Opcode/Ice/IceRandom.cpp create mode 100644 Opcode/Ice/IceRandom.h create mode 100644 Opcode/Ice/IceRay.cpp create mode 100644 Opcode/Ice/IceRay.h create mode 100644 Opcode/Ice/IceRevisitedRadix.cpp create mode 100644 Opcode/Ice/IceRevisitedRadix.h create mode 100644 Opcode/Ice/IceSegment.cpp create mode 100644 Opcode/Ice/IceSegment.h create mode 100644 Opcode/Ice/IceTriangle.cpp create mode 100644 Opcode/Ice/IceTriangle.h create mode 100644 Opcode/Ice/IceTrilist.h create mode 100644 Opcode/Ice/IceTypes.h create mode 100644 Opcode/Ice/IceUtils.cpp create mode 100644 Opcode/Ice/IceUtils.h (limited to 'Opcode/Ice') diff --git a/Opcode/Ice/IceAABB.cpp b/Opcode/Ice/IceAABB.cpp new file mode 100644 index 0000000..149211c --- /dev/null +++ b/Opcode/Ice/IceAABB.cpp @@ -0,0 +1,405 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains AABB-related code. + * \file IceAABB.cpp + * \author Pierre Terdiman + * \date January, 29, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * AABB class. + * \class AABB + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the sum of two AABBs. + * \param aabb [in] the other AABB + * \return Self-Reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABB& AABB::Add(const AABB& aabb) +{ + // Compute new min & max values + IcePoint Min; GetMin(Min); + IcePoint Tmp; aabb.GetMin(Tmp); + Min.Min(Tmp); + + IcePoint Max; GetMax(Max); + aabb.GetMax(Tmp); + Max.Max(Tmp); + + // Update this + SetMinMax(Min, Max); + return *this; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Makes a cube from the AABB. + * \param cube [out] the cube AABB + * \return cube edge length + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float AABB::MakeCube(AABB& cube) const +{ + IcePoint Ext; GetExtents(Ext); + float Max = Ext.Max(); + + IcePoint Cnt; GetCenter(Cnt); + cube.SetCenterExtents(Cnt, IcePoint(Max, Max, Max)); + return Max; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Makes a sphere from the AABB. + * \param sphere [out] sphere containing the AABB + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void AABB::MakeSphere(Sphere& sphere) const +{ + GetExtents(sphere.mCenter); + sphere.mRadius = sphere.mCenter.Magnitude() * 1.00001f; // To make sure sphere::Contains(*this) succeeds + GetCenter(sphere.mCenter); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks a box is inside another box. + * \param box [in] the other AABB + * \return true if current box is inside input box + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABB::IsInside(const AABB& box) const +{ + if(box.GetMin(0)>GetMin(0)) return false; + if(box.GetMin(1)>GetMin(1)) return false; + if(box.GetMin(2)>GetMin(2)) return false; + if(box.GetMax(0) max.x) ? 2 : 0) // 2 = right + + ((local_eye.y < min.y) ? 4 : 0) // 4 = bottom + + ((local_eye.y > max.y) ? 8 : 0) // 8 = top + + ((local_eye.z < min.z) ? 16 : 0) // 16 = front + + ((local_eye.z > max.z) ? 32 : 0); // 32 = back + + // Look up number of vertices in outline + num = (sdword)gIndexList[pos][7]; + // Zero indicates invalid case + if(!num) return null; + + return &gIndexList[pos][0]; +} + +// calculateBoxArea: computes the screen-projected 2D area of an oriented 3D bounding box + +//const IcePoint& eye, //eye point (in bbox object coordinates) +//const AABB& box, //3d bbox +//const Matrix4x4& mat, //free transformation for bbox +//float width, float height, int& num) +float AABB::ComputeBoxArea(const IcePoint& eye, const Matrix4x4& mat, float width, float height, sdword& num) const +{ + const sbyte* Outline = ComputeOutline(eye, num); + if(!Outline) return -1.0f; + + // Compute box vertices + IcePoint vertexBox[8], dst[8]; + ComputePoints(vertexBox); + + // Transform all outline corners into 2D screen space + for(sdword i=0;i GetMax(0) || p.x < GetMin(0)) return FALSE; \ + if(p.y > GetMax(1) || p.y < GetMin(1)) return FALSE; \ + if(p.z > GetMax(2) || p.z < GetMin(2)) return FALSE; \ + return TRUE; \ + } + + enum AABBType + { + AABB_RENDER = 0, //!< AABB used for rendering. Not visible == not rendered. + AABB_UPDATE = 1, //!< AABB used for dynamic updates. Not visible == not updated. + + AABB_FORCE_DWORD = 0x7fffffff, + }; + +#ifdef USE_MINMAX + + struct ICEMATHS_API ShadowAABB + { + Point mMin; + Point mMax; + }; + + class ICEMATHS_API AABB + { + public: + //! Constructor + inline_ AABB() {} + //! Destructor + inline_ ~AABB() {} + + //! Type-independent methods + AABB_COMMON_METHODS; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an AABB from min & max vectors. + * \param min [in] the min point + * \param max [in] the max point + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetMinMax(const Point& min, const Point& max) { mMin = min; mMax = max; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an AABB from center & extents vectors. + * \param c [in] the center point + * \param e [in] the extents vector + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetCenterExtents(const Point& c, const Point& e) { mMin = c - e; mMax = c + e; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an empty AABB. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetEmpty() { Point p(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); mMin = -p; mMax = p;} + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups a point AABB. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetPoint(const Point& pt) { mMin = mMax = pt; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Gets the size of the AABB. The size is defined as the longest extent. + * \return the size of the AABB + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + float GetSize() const { Point e; GetExtents(e); return e.Max(); } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Extends the AABB. + * \param p [in] the next point + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void Extend(const Point& p) + { + if(p.x > mMax.x) mMax.x = p.x; + if(p.x < mMin.x) mMin.x = p.x; + + if(p.y > mMax.y) mMax.y = p.y; + if(p.y < mMin.y) mMin.y = p.y; + + if(p.z > mMax.z) mMax.z = p.z; + if(p.z < mMin.z) mMin.z = p.z; + } + // Data access + + //! Get min point of the box + inline_ void GetMin(Point& min) const { min = mMin; } + //! Get max point of the box + inline_ void GetMax(Point& max) const { max = mMax; } + + //! Get component of the box's min point along a given axis + inline_ float GetMin(udword axis) const { return mMin[axis]; } + //! Get component of the box's max point along a given axis + inline_ float GetMax(udword axis) const { return mMax[axis]; } + + //! Get box center + inline_ void GetCenter(Point& center) const { center = (mMax + mMin)*0.5f; } + //! Get box extents + inline_ void GetExtents(Point& extents) const { extents = (mMax - mMin)*0.5f; } + + //! Get component of the box's center along a given axis + inline_ float GetCenter(udword axis) const { return (mMax[axis] + mMin[axis])*0.5f; } + //! Get component of the box's extents along a given axis + inline_ float GetExtents(udword axis) const { return (mMax[axis] - mMin[axis])*0.5f; } + + //! Get box diagonal + inline_ void GetDiagonal(Point& diagonal) const { diagonal = mMax - mMin; } + inline_ float GetWidth() const { return mMax.x - mMin.x; } + inline_ float GetHeight() const { return mMax.y - mMin.y; } + inline_ float GetDepth() const { return mMax.z - mMin.z; } + + //! Volume + inline_ float GetVolume() const { return GetWidth() * GetHeight() * GetDepth(); } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the intersection between two AABBs. + * \param a [in] the other AABB + * \return true on intersection + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL Intersect(const AABB& a) const + { + if(mMax.x < a.mMin.x + || a.mMax.x < mMin.x + || mMax.y < a.mMin.y + || a.mMax.y < mMin.y + || mMax.z < a.mMin.z + || a.mMax.z < mMin.z) return FALSE; + + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the 1D-intersection between two AABBs, on a given axis. + * \param a [in] the other AABB + * \param axis [in] the axis (0, 1, 2) + * \return true on intersection + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL Intersect(const AABB& a, udword axis) const + { + if(mMax[axis] < a.mMin[axis] || a.mMax[axis] < mMin[axis]) return FALSE; + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Recomputes the AABB after an arbitrary transform by a 4x4 matrix. + * Original code by Charles Bloom on the GD-Algorithm list. (I slightly modified it) + * \param mtx [in] the transform matrix + * \param aabb [out] the transformed AABB [can be *this] + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void Rotate(const Matrix4x4& mtx, AABB& aabb) const + { + // The three edges transformed: you can efficiently transform an X-only vector + // by just getting the "X" column of the matrix + Point vx,vy,vz; + mtx.GetRow(0, vx); vx *= (mMax.x - mMin.x); + mtx.GetRow(1, vy); vy *= (mMax.y - mMin.y); + mtx.GetRow(2, vz); vz *= (mMax.z - mMin.z); + + // Transform the min point + aabb.mMin = aabb.mMax = mMin * mtx; + + // Take the transformed min & axes and find new extents + // Using CPU code in the right place is faster... + if(IS_NEGATIVE_FLOAT(vx.x)) aabb.mMin.x += vx.x; else aabb.mMax.x += vx.x; + if(IS_NEGATIVE_FLOAT(vx.y)) aabb.mMin.y += vx.y; else aabb.mMax.y += vx.y; + if(IS_NEGATIVE_FLOAT(vx.z)) aabb.mMin.z += vx.z; else aabb.mMax.z += vx.z; + if(IS_NEGATIVE_FLOAT(vy.x)) aabb.mMin.x += vy.x; else aabb.mMax.x += vy.x; + if(IS_NEGATIVE_FLOAT(vy.y)) aabb.mMin.y += vy.y; else aabb.mMax.y += vy.y; + if(IS_NEGATIVE_FLOAT(vy.z)) aabb.mMin.z += vy.z; else aabb.mMax.z += vy.z; + if(IS_NEGATIVE_FLOAT(vz.x)) aabb.mMin.x += vz.x; else aabb.mMax.x += vz.x; + if(IS_NEGATIVE_FLOAT(vz.y)) aabb.mMin.y += vz.y; else aabb.mMax.y += vz.y; + if(IS_NEGATIVE_FLOAT(vz.z)) aabb.mMin.z += vz.z; else aabb.mMax.z += vz.z; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Checks the AABB is valid. + * \return true if the box is valid + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL IsValid() const + { + // Consistency condition for (Min, Max) boxes: min < max + if(mMin.x > mMax.x) return FALSE; + if(mMin.y > mMax.y) return FALSE; + if(mMin.z > mMax.z) return FALSE; + return TRUE; + } + + //! Operator for AABB *= float. Scales the extents, keeps same center. + inline_ AABB& operator*=(float s) + { + Point Center; GetCenter(Center); + Point Extents; GetExtents(Extents); + SetCenterExtents(Center, Extents * s); + return *this; + } + + //! Operator for AABB /= float. Scales the extents, keeps same center. + inline_ AABB& operator/=(float s) + { + Point Center; GetCenter(Center); + Point Extents; GetExtents(Extents); + SetCenterExtents(Center, Extents / s); + return *this; + } + + //! Operator for AABB += Point. Translates the box. + inline_ AABB& operator+=(const Point& trans) + { + mMin+=trans; + mMax+=trans; + return *this; + } + private: + Point mMin; //!< Min point + Point mMax; //!< Max point + }; + +#else + + class ICEMATHS_API AABB + { + public: + //! Constructor + inline_ AABB() {} + //! Destructor + inline_ ~AABB() {} + + //! Type-independent methods + AABB_COMMON_METHODS; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an AABB from min & max vectors. + * \param min [in] the min point + * \param max [in] the max point + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetMinMax(const Point& min, const Point& max) { mCenter = (max + min)*0.5f; mExtents = (max - min)*0.5f; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an AABB from center & extents vectors. + * \param c [in] the center point + * \param e [in] the extents vector + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetCenterExtents(const Point& c, const Point& e) { mCenter = c; mExtents = e; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an empty AABB. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetEmpty() { mCenter.Zero(); mExtents.Set(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);} + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups a point AABB. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetPoint(const Point& pt) { mCenter = pt; mExtents.Zero(); } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Gets the size of the AABB. The size is defined as the longest extent. + * \return the size of the AABB + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + float GetSize() const { return mExtents.Max(); } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Extends the AABB. + * \param p [in] the next point + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void Extend(const Point& p) + { + Point Max = mCenter + mExtents; + Point Min = mCenter - mExtents; + + if(p.x > Max.x) Max.x = p.x; + if(p.x < Min.x) Min.x = p.x; + + if(p.y > Max.y) Max.y = p.y; + if(p.y < Min.y) Min.y = p.y; + + if(p.z > Max.z) Max.z = p.z; + if(p.z < Min.z) Min.z = p.z; + + SetMinMax(Min, Max); + } + // Data access + + //! Get min point of the box + inline_ void GetMin(Point& min) const { min = mCenter - mExtents; } + //! Get max point of the box + inline_ void GetMax(Point& max) const { max = mCenter + mExtents; } + + //! Get component of the box's min point along a given axis + inline_ float GetMin(udword axis) const { return mCenter[axis] - mExtents[axis]; } + //! Get component of the box's max point along a given axis + inline_ float GetMax(udword axis) const { return mCenter[axis] + mExtents[axis]; } + + //! Get box center + inline_ void GetCenter(Point& center) const { center = mCenter; } + //! Get box extents + inline_ void GetExtents(Point& extents) const { extents = mExtents; } + + //! Get component of the box's center along a given axis + inline_ float GetCenter(udword axis) const { return mCenter[axis]; } + //! Get component of the box's extents along a given axis + inline_ float GetExtents(udword axis) const { return mExtents[axis]; } + + //! Get box diagonal + inline_ void GetDiagonal(Point& diagonal) const { diagonal = mExtents * 2.0f; } + inline_ float GetWidth() const { return mExtents.x * 2.0f; } + inline_ float GetHeight() const { return mExtents.y * 2.0f; } + inline_ float GetDepth() const { return mExtents.z * 2.0f; } + + //! Volume + inline_ float GetVolume() const { return mExtents.x * mExtents.y * mExtents.z * 8.0f; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the intersection between two AABBs. + * \param a [in] the other AABB + * \return true on intersection + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL Intersect(const AABB& a) const + { + float tx = mCenter.x - a.mCenter.x; float ex = a.mExtents.x + mExtents.x; if(AIR(tx) > IR(ex)) return FALSE; + float ty = mCenter.y - a.mCenter.y; float ey = a.mExtents.y + mExtents.y; if(AIR(ty) > IR(ey)) return FALSE; + float tz = mCenter.z - a.mCenter.z; float ez = a.mExtents.z + mExtents.z; if(AIR(tz) > IR(ez)) return FALSE; + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * The standard intersection method from Gamasutra. Just here to check its speed against the one above. + * \param a [in] the other AABB + * \return true on intersection + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool GomezIntersect(const AABB& a) + { + Point T = mCenter - a.mCenter; // Vector from A to B + return ((fabsf(T.x) <= (a.mExtents.x + mExtents.x)) + && (fabsf(T.y) <= (a.mExtents.y + mExtents.y)) + && (fabsf(T.z) <= (a.mExtents.z + mExtents.z))); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the 1D-intersection between two AABBs, on a given axis. + * \param a [in] the other AABB + * \param axis [in] the axis (0, 1, 2) + * \return true on intersection + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL Intersect(const AABB& a, udword axis) const + { + float t = mCenter[axis] - a.mCenter[axis]; + float e = a.mExtents[axis] + mExtents[axis]; + if(AIR(t) > IR(e)) return FALSE; + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Recomputes the AABB after an arbitrary transform by a 4x4 matrix. + * \param mtx [in] the transform matrix + * \param aabb [out] the transformed AABB [can be *this] + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void Rotate(const Matrix4x4& mtx, AABB& aabb) const + { + // Compute new center + aabb.mCenter = mCenter * mtx; + + // Compute new extents. FPU code & CPU code have been interleaved for improved performance. + Point Ex(mtx.m[0][0] * mExtents.x, mtx.m[0][1] * mExtents.x, mtx.m[0][2] * mExtents.x); + IR(Ex.x)&=0x7fffffff; IR(Ex.y)&=0x7fffffff; IR(Ex.z)&=0x7fffffff; + + Point Ey(mtx.m[1][0] * mExtents.y, mtx.m[1][1] * mExtents.y, mtx.m[1][2] * mExtents.y); + IR(Ey.x)&=0x7fffffff; IR(Ey.y)&=0x7fffffff; IR(Ey.z)&=0x7fffffff; + + Point Ez(mtx.m[2][0] * mExtents.z, mtx.m[2][1] * mExtents.z, mtx.m[2][2] * mExtents.z); + IR(Ez.x)&=0x7fffffff; IR(Ez.y)&=0x7fffffff; IR(Ez.z)&=0x7fffffff; + + aabb.mExtents.x = Ex.x + Ey.x + Ez.x; + aabb.mExtents.y = Ex.y + Ey.y + Ez.y; + aabb.mExtents.z = Ex.z + Ey.z + Ez.z; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Checks the AABB is valid. + * \return true if the box is valid + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL IsValid() const + { + // Consistency condition for (Center, Extents) boxes: Extents >= 0 + if(IS_NEGATIVE_FLOAT(mExtents.x)) return FALSE; + if(IS_NEGATIVE_FLOAT(mExtents.y)) return FALSE; + if(IS_NEGATIVE_FLOAT(mExtents.z)) return FALSE; + return TRUE; + } + + //! Operator for AABB *= float. Scales the extents, keeps same center. + inline_ AABB& operator*=(float s) { mExtents*=s; return *this; } + + //! Operator for AABB /= float. Scales the extents, keeps same center. + inline_ AABB& operator/=(float s) { mExtents/=s; return *this; } + + //! Operator for AABB += Point. Translates the box. + inline_ AABB& operator+=(const Point& trans) + { + mCenter+=trans; + return *this; + } + private: + Point mCenter; //!< AABB Center + Point mExtents; //!< x, y and z extents + }; + +#endif + + inline_ void ComputeMinMax(const Point& p, Point& min, Point& max) + { + if(p.x > max.x) max.x = p.x; + if(p.x < min.x) min.x = p.x; + + if(p.y > max.y) max.y = p.y; + if(p.y < min.y) min.y = p.y; + + if(p.z > max.z) max.z = p.z; + if(p.z < min.z) min.z = p.z; + } + + inline_ void ComputeAABB(AABB& aabb, const Point* list, udword nb_pts) + { + if(list) + { + Point Maxi(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); + Point Mini(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT); + while(nb_pts--) + { +// _prefetch(list+1); // off by one ? + ComputeMinMax(*list++, Mini, Maxi); + } + aabb.SetMinMax(Mini, Maxi); + } + } + +#endif // __ICEAABB_H__ diff --git a/Opcode/Ice/IceAxes.h b/Opcode/Ice/IceAxes.h new file mode 100644 index 0000000..39004a9 --- /dev/null +++ b/Opcode/Ice/IceAxes.h @@ -0,0 +1,54 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains axes definition. + * \file IceAxes.h + * \author Pierre Terdiman + * \date January, 29, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEAXES_H__ +#define __ICEAXES_H__ + + enum PointComponent + { + _X = 0, + _Y = 1, + _Z = 2, + _W = 3, + + _FORCE_DWORD = 0x7fffffff + }; + + enum AxisOrder + { + AXES_XYZ = (_X)|(_Y<<2)|(_Z<<4), + AXES_XZY = (_X)|(_Z<<2)|(_Y<<4), + AXES_YXZ = (_Y)|(_X<<2)|(_Z<<4), + AXES_YZX = (_Y)|(_Z<<2)|(_X<<4), + AXES_ZXY = (_Z)|(_X<<2)|(_Y<<4), + AXES_ZYX = (_Z)|(_Y<<2)|(_X<<4), + + AXES_FORCE_DWORD = 0x7fffffff + }; + + class ICEMATHS_API Axes + { + public: + + inline_ Axes(AxisOrder order) + { + mAxis0 = (order ) & 3; + mAxis1 = (order>>2) & 3; + mAxis2 = (order>>4) & 3; + } + inline_ ~Axes() {} + + udword mAxis0; + udword mAxis1; + udword mAxis2; + }; + +#endif // __ICEAXES_H__ diff --git a/Opcode/Ice/IceBoundingSphere.h b/Opcode/Ice/IceBoundingSphere.h new file mode 100644 index 0000000..c66524c --- /dev/null +++ b/Opcode/Ice/IceBoundingSphere.h @@ -0,0 +1,142 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code to compute the minimal bounding sphere. + * \file IceBoundingSphere.h + * \author Pierre Terdiman + * \date January, 29, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEBOUNDINGSPHERE_H__ +#define __ICEBOUNDINGSPHERE_H__ + + enum BSphereMethod + { + BS_NONE, + BS_GEMS, + BS_MINIBALL, + + BS_FORCE_DWORD = 0x7fffffff + }; + + class ICEMATHS_API Sphere + { + public: + //! Constructor + inline_ Sphere() {} + //! Constructor + inline_ Sphere(const Point& center, float radius) : mCenter(center), mRadius(radius) {} + //! Constructor + Sphere(udword nb_verts, const Point* verts); + //! Copy constructor + inline_ Sphere(const Sphere& sphere) : mCenter(sphere.mCenter), mRadius(sphere.mRadius) {} + //! Destructor + inline_ ~Sphere() {} + + BSphereMethod Compute(udword nb_verts, const Point* verts); + bool FastCompute(udword nb_verts, const Point* verts); + + // Access methods + inline_ const Point& GetCenter() const { return mCenter; } + inline_ float GetRadius() const { return mRadius; } + + inline_ const Point& Center() const { return mCenter; } + inline_ float Radius() const { return mRadius; } + + inline_ Sphere& Set(const Point& center, float radius) { mCenter = center; mRadius = radius; return *this; } + inline_ Sphere& SetCenter(const Point& center) { mCenter = center; return *this; } + inline_ Sphere& SetRadius(float radius) { mRadius = radius; return *this; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a point is contained within the sphere. + * \param p [in] the point to test + * \return true if inside the sphere + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Contains(const Point& p) const + { + return mCenter.SquareDistance(p) <= mRadius*mRadius; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a sphere is contained within the sphere. + * \param sphere [in] the sphere to test + * \return true if inside the sphere + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Contains(const Sphere& sphere) const + { + // If our radius is the smallest, we can't possibly contain the other sphere + if(mRadius < sphere.mRadius) return false; + // So r is always positive or null now + float r = mRadius - sphere.mRadius; + return mCenter.SquareDistance(sphere.mCenter) <= r*r; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a box is contained within the sphere. + * \param aabb [in] the box to test + * \return true if inside the sphere + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL Contains(const AABB& aabb) const + { + // I assume if all 8 box vertices are inside the sphere, so does the whole box. + // Sounds ok but maybe there's a better way? + float R2 = mRadius * mRadius; +#ifdef USE_MIN_MAX + const Point& Max = ((ShadowAABB&)&aabb).mMax; + const Point& Min = ((ShadowAABB&)&aabb).mMin; +#else + Point Max; aabb.GetMax(Max); + Point Min; aabb.GetMin(Min); +#endif + Point p; + p.x=Max.x; p.y=Max.y; p.z=Max.z; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Min.x; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Max.x; p.y=Min.y; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Min.x; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Max.x; p.y=Max.y; p.z=Min.z; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Min.x; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Max.x; p.y=Min.y; if(mCenter.SquareDistance(p)>=R2) return FALSE; + p.x=Min.x; if(mCenter.SquareDistance(p)>=R2) return FALSE; + + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if the sphere intersects another sphere + * \param sphere [in] the other sphere + * \return true if spheres overlap + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Intersect(const Sphere& sphere) const + { + float r = mRadius + sphere.mRadius; + return mCenter.SquareDistance(sphere.mCenter) <= r*r; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Checks the sphere is valid. + * \return true if the box is valid + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL IsValid() const + { + // Consistency condition for spheres: Radius >= 0.0f + if(mRadius < 0.0f) return FALSE; + return TRUE; + } + public: + Point mCenter; //!< Sphere center + float mRadius; //!< Sphere radius + }; + +#endif // __ICEBOUNDINGSPHERE_H__ diff --git a/Opcode/Ice/IceContainer.cpp b/Opcode/Ice/IceContainer.cpp new file mode 100644 index 0000000..e2c42d1 --- /dev/null +++ b/Opcode/Ice/IceContainer.cpp @@ -0,0 +1,345 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a simple container class. + * \file IceContainer.cpp + * \author Pierre Terdiman + * \date February, 5, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a list of 32-bits values. + * Use this class when you need to store an unknown number of values. The list is automatically + * resized and can contains 32-bits entities (dwords or floats) + * + * \class Container + * \author Pierre Terdiman + * \version 1.0 + * \date 08.15.98 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceCore; + +// Static members +#ifdef CONTAINER_STATS +udword Container::mNbContainers = 0; +udword Container::mUsedRam = 0; +#endif + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. No entries allocated there. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Container::Container() : mMaxNbEntries(0), mCurNbEntries(0), mEntries(null), mGrowthFactor(2.0f) +{ +#ifdef CONTAINER_STATS + mNbContainers++; + mUsedRam+=sizeof(Container); +#endif +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. Also allocates a given number of entries. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Container::Container(udword size, float growth_factor) : mMaxNbEntries(0), mCurNbEntries(0), mEntries(null), mGrowthFactor(growth_factor) +{ +#ifdef CONTAINER_STATS + mNbContainers++; + mUsedRam+=sizeof(Container); +#endif + SetSize(size); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Copy constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Container::Container(const Container& object) : mMaxNbEntries(0), mCurNbEntries(0), mEntries(null), mGrowthFactor(2.0f) +{ +#ifdef CONTAINER_STATS + mNbContainers++; + mUsedRam+=sizeof(Container); +#endif + *this = object; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. Frees everything and leaves. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Container::~Container() +{ + Empty(); +#ifdef CONTAINER_STATS + mNbContainers--; + mUsedRam-=GetUsedRam(); +#endif +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Clears the container. All stored values are deleted, and it frees used ram. + * \see Reset() + * \return Self-Reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Container& Container::Empty() +{ +#ifdef CONTAINER_STATS + mUsedRam-=mMaxNbEntries*sizeof(udword); +#endif + DELETEARRAY(mEntries); + mCurNbEntries = mMaxNbEntries = 0; + return *this; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Resizes the container. + * \param needed [in] assume the container can be added at least "needed" values + * \return true if success. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool Container::Resize(udword needed) +{ +#ifdef CONTAINER_STATS + // Subtract previous amount of bytes + mUsedRam-=mMaxNbEntries*sizeof(udword); +#endif + + // Get more entries + mMaxNbEntries = mMaxNbEntries ? udword(float(mMaxNbEntries)*mGrowthFactor) : 2; // Default nb Entries = 2 + if(mMaxNbEntriesmMaxNbEntries) Resize(nb); + + // Add new entry + CopyMemory(&mEntries[mCurNbEntries], entries, nb*sizeof(udword)); + mCurNbEntries+=nb; + return *this; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * A O(1) method to add a value in the container. The container is automatically resized if needed. + * The method is inline, not the resize. The call overhead happens on resizes only, which is not a problem since the resizing operation + * costs a lot more than the call overhead... + * + * \param entry [in] a float to store in the container + * \see Add(udword entry) + * \see Empty() + * \see Contains(udword entry) + * \return Self-Reference + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ Container& Add(float entry) + { + // Resize if needed + if(mCurNbEntries==mMaxNbEntries) Resize(); + + // Add new entry + mEntries[mCurNbEntries++] = IR(entry); + return *this; + } + + inline_ Container& Add(const float* entries, udword nb) + { + // Resize if needed + if(mCurNbEntries+nb>mMaxNbEntries) Resize(nb); + + // Add new entry + CopyMemory(&mEntries[mCurNbEntries], entries, nb*sizeof(float)); + mCurNbEntries+=nb; + return *this; + } + + //! Add unique [slow] + inline_ Container& AddUnique(udword entry) + { + if(!Contains(entry)) Add(entry); + return *this; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Clears the container. All stored values are deleted, and it frees used ram. + * \see Reset() + * \return Self-Reference + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + Container& Empty(); + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Resets the container. Stored values are discarded but the buffer is kept so that further calls don't need resizing again. + * That's a kind of temporal coherence. + * \see Empty() + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void Reset() + { + // Avoid the write if possible + // ### CMOV + if(mCurNbEntries) mCurNbEntries = 0; + } + + // HANDLE WITH CARE + inline_ void ForceSize(udword size) + { + mCurNbEntries = size; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Sets the initial size of the container. If it already contains something, it's discarded. + * \param nb [in] Number of entries + * \return true if success + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool SetSize(udword nb); + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Refits the container and get rid of unused bytes. + * \return true if success + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool Refit(); + + // Checks whether the container already contains a given value. + bool Contains(udword entry, udword* location=null) const; + // Deletes an entry - doesn't preserve insertion order. + bool Delete(udword entry); + // Deletes an entry - does preserve insertion order. + bool DeleteKeepingOrder(udword entry); + //! Deletes the very last entry. + inline_ void DeleteLastEntry() { if(mCurNbEntries) mCurNbEntries--; } + //! Deletes the entry whose index is given + inline_ void DeleteIndex(udword index) { mEntries[index] = mEntries[--mCurNbEntries]; } + + // Helpers + Container& FindNext(udword& entry, FindMode find_mode=FIND_CLAMP); + Container& FindPrev(udword& entry, FindMode find_mode=FIND_CLAMP); + // Data access. + inline_ udword GetNbEntries() const { return mCurNbEntries; } //!< Returns the current number of entries. + inline_ udword GetEntry(udword i) const { return mEntries[i]; } //!< Returns ith entry + inline_ udword* GetEntries() const { return mEntries; } //!< Returns the list of entries. + + inline_ udword GetFirst() const { return mEntries[0]; } + inline_ udword GetLast() const { return mEntries[mCurNbEntries-1]; } + + // Growth control + inline_ float GetGrowthFactor() const { return mGrowthFactor; } //!< Returns the growth factor + inline_ void SetGrowthFactor(float growth) { mGrowthFactor = growth; } //!< Sets the growth factor + inline_ bool IsFull() const { return mCurNbEntries==mMaxNbEntries; } //!< Checks the container is full + inline_ BOOL IsNotEmpty() const { return mCurNbEntries; } //!< Checks the container is empty + + //! Read-access as an array + inline_ udword operator[](udword i) const { ASSERT(i>=0 && i=0 && i>31); + return (float&)y; + } + + //! Computes 1.0f / sqrtf(x). + inline_ float frsqrt(float f) + { + float x = f * 0.5f; + udword y = 0x5f3759df - ((udword&)f >> 1); + // Iteration... + (float&)y = (float&)y * ( 1.5f - ( x * (float&)y * (float&)y ) ); + // Result + return (float&)y; + } + + //! Computes 1.0f / sqrtf(x). Comes from NVIDIA. + inline_ float InvSqrt(const float& x) + { + udword tmp = (udword(IEEE_1_0 << 1) + IEEE_1_0 - *(udword*)&x) >> 1; + float y = *(float*)&tmp; + return y * (1.47f - 0.47f * x * y * y); + } + + //! Computes 1.0f / sqrtf(x). Comes from Quake3. Looks like the first one I had above. + //! See http://www.magic-software.com/3DGEDInvSqrt.html + inline_ float RSqrt(float number) + { + long i; + float x2, y; + const float threehalfs = 1.5f; + + x2 = number * 0.5f; + y = number; + i = * (long *) &y; + i = 0x5f3759df - (i >> 1); + y = * (float *) &i; + y = y * (threehalfs - (x2 * y * y)); + + return y; + } + + //! TO BE DOCUMENTED + inline_ float fsqrt(float f) + { + udword y = ( ( (sdword&)f - 0x3f800000 ) >> 1 ) + 0x3f800000; + // Iteration...? + // (float&)y = (3.0f - ((float&)y * (float&)y) / f) * (float&)y * 0.5f; + // Result + return (float&)y; + } + + //! Returns the float ranged espilon value. + inline_ float fepsilon(float f) + { + udword b = (udword&)f & 0xff800000; + udword a = b | 0x00000001; + (float&)a -= (float&)b; + // Result + return (float&)a; + } + + //! Is the float valid ? + inline_ bool IsNAN(float value) { return (IR(value)&0x7f800000) == 0x7f800000; } + inline_ bool IsIndeterminate(float value) { return IR(value) == 0xffc00000; } + inline_ bool IsPlusInf(float value) { return IR(value) == 0x7f800000; } + inline_ bool IsMinusInf(float value) { return IR(value) == 0xff800000; } + + inline_ bool IsValidFloat(float value) + { + if(IsNAN(value)) return false; + if(IsIndeterminate(value)) return false; + if(IsPlusInf(value)) return false; + if(IsMinusInf(value)) return false; + return true; + } + + #define CHECK_VALID_FLOAT(x) ASSERT(IsValidFloat(x)); + +/* + //! FPU precision setting function. + inline_ void SetFPU() + { + // This function evaluates whether the floating-point + // control word is set to single precision/round to nearest/ + // exceptions disabled. If these conditions don't hold, the + // function changes the control word to set them and returns + // TRUE, putting the old control word value in the passback + // location pointed to by pwOldCW. + { + uword wTemp, wSave; + + __asm fstcw wSave + if (wSave & 0x300 || // Not single mode + 0x3f != (wSave & 0x3f) || // Exceptions enabled + wSave & 0xC00) // Not round to nearest mode + { + __asm + { + mov ax, wSave + and ax, not 300h ;; single mode + or ax, 3fh ;; disable all exceptions + and ax, not 0xC00 ;; round to nearest mode + mov wTemp, ax + fldcw wTemp + } + } + } + } +*/ + //! This function computes the slowest possible floating-point value (you can also directly use FLT_EPSILON) + inline_ float ComputeFloatEpsilon() + { + float f = 1.0f; + ((udword&)f)^=1; + return f - 1.0f; // You can check it's the same as FLT_EPSILON + } + + inline_ bool IsFloatZero(float x, float epsilon=1e-6f) + { + return x*x < epsilon; + } + + #define FCOMI_ST0 _asm _emit 0xdb _asm _emit 0xf0 + #define FCOMIP_ST0 _asm _emit 0xdf _asm _emit 0xf0 + #define FCMOVB_ST0 _asm _emit 0xda _asm _emit 0xc0 + #define FCMOVNB_ST0 _asm _emit 0xdb _asm _emit 0xc0 + + #define FCOMI_ST1 _asm _emit 0xdb _asm _emit 0xf1 + #define FCOMIP_ST1 _asm _emit 0xdf _asm _emit 0xf1 + #define FCMOVB_ST1 _asm _emit 0xda _asm _emit 0xc1 + #define FCMOVNB_ST1 _asm _emit 0xdb _asm _emit 0xc1 + + #define FCOMI_ST2 _asm _emit 0xdb _asm _emit 0xf2 + #define FCOMIP_ST2 _asm _emit 0xdf _asm _emit 0xf2 + #define FCMOVB_ST2 _asm _emit 0xda _asm _emit 0xc2 + #define FCMOVNB_ST2 _asm _emit 0xdb _asm _emit 0xc2 + + #define FCOMI_ST3 _asm _emit 0xdb _asm _emit 0xf3 + #define FCOMIP_ST3 _asm _emit 0xdf _asm _emit 0xf3 + #define FCMOVB_ST3 _asm _emit 0xda _asm _emit 0xc3 + #define FCMOVNB_ST3 _asm _emit 0xdb _asm _emit 0xc3 + + #define FCOMI_ST4 _asm _emit 0xdb _asm _emit 0xf4 + #define FCOMIP_ST4 _asm _emit 0xdf _asm _emit 0xf4 + #define FCMOVB_ST4 _asm _emit 0xda _asm _emit 0xc4 + #define FCMOVNB_ST4 _asm _emit 0xdb _asm _emit 0xc4 + + #define FCOMI_ST5 _asm _emit 0xdb _asm _emit 0xf5 + #define FCOMIP_ST5 _asm _emit 0xdf _asm _emit 0xf5 + #define FCMOVB_ST5 _asm _emit 0xda _asm _emit 0xc5 + #define FCMOVNB_ST5 _asm _emit 0xdb _asm _emit 0xc5 + + #define FCOMI_ST6 _asm _emit 0xdb _asm _emit 0xf6 + #define FCOMIP_ST6 _asm _emit 0xdf _asm _emit 0xf6 + #define FCMOVB_ST6 _asm _emit 0xda _asm _emit 0xc6 + #define FCMOVNB_ST6 _asm _emit 0xdb _asm _emit 0xc6 + + #define FCOMI_ST7 _asm _emit 0xdb _asm _emit 0xf7 + #define FCOMIP_ST7 _asm _emit 0xdf _asm _emit 0xf7 + #define FCMOVB_ST7 _asm _emit 0xda _asm _emit 0xc7 + #define FCMOVNB_ST7 _asm _emit 0xdb _asm _emit 0xc7 + + //! A global function to find MAX(a,b) using FCOMI/FCMOV + inline_ float FCMax2(float a, float b) + { + float Res; + _asm fld [a] + _asm fld [b] + FCOMI_ST1 + FCMOVB_ST1 + _asm fstp [Res] + _asm fcomp + return Res; + } + + //! A global function to find MIN(a,b) using FCOMI/FCMOV + inline_ float FCMin2(float a, float b) + { + float Res; + _asm fld [a] + _asm fld [b] + FCOMI_ST1 + FCMOVNB_ST1 + _asm fstp [Res] + _asm fcomp + return Res; + } + + //! A global function to find MAX(a,b,c) using FCOMI/FCMOV + inline_ float FCMax3(float a, float b, float c) + { + float Res; + _asm fld [a] + _asm fld [b] + _asm fld [c] + FCOMI_ST1 + FCMOVB_ST1 + FCOMI_ST2 + FCMOVB_ST2 + _asm fstp [Res] + _asm fcompp + return Res; + } + + //! A global function to find MIN(a,b,c) using FCOMI/FCMOV + inline_ float FCMin3(float a, float b, float c) + { + float Res; + _asm fld [a] + _asm fld [b] + _asm fld [c] + FCOMI_ST1 + FCMOVNB_ST1 + FCOMI_ST2 + FCMOVNB_ST2 + _asm fstp [Res] + _asm fcompp + return Res; + } + + inline_ int ConvertToSortable(float f) + { + int& Fi = (int&)f; + int Fmask = (Fi>>31); + Fi ^= Fmask; + Fmask &= ~(1<<31); + Fi -= Fmask; + return Fi; + } + + enum FPUMode + { + FPU_FLOOR = 0, + FPU_CEIL = 1, + FPU_BEST = 2, + + FPU_FORCE_DWORD = 0x7fffffff + }; + + FUNCTION ICECORE_API FPUMode GetFPUMode(); + FUNCTION ICECORE_API void SaveFPU(); + FUNCTION ICECORE_API void RestoreFPU(); + FUNCTION ICECORE_API void SetFPUFloorMode(); + FUNCTION ICECORE_API void SetFPUCeilMode(); + FUNCTION ICECORE_API void SetFPUBestMode(); + + FUNCTION ICECORE_API void SetFPUPrecision24(); + FUNCTION ICECORE_API void SetFPUPrecision53(); + FUNCTION ICECORE_API void SetFPUPrecision64(); + FUNCTION ICECORE_API void SetFPURoundingChop(); + FUNCTION ICECORE_API void SetFPURoundingUp(); + FUNCTION ICECORE_API void SetFPURoundingDown(); + FUNCTION ICECORE_API void SetFPURoundingNear(); + + FUNCTION ICECORE_API int intChop(const float& f); + FUNCTION ICECORE_API int intFloor(const float& f); + FUNCTION ICECORE_API int intCeil(const float& f); + +#endif // __ICEFPU_H__ diff --git a/Opcode/Ice/IceHPoint.cpp b/Opcode/Ice/IceHPoint.cpp new file mode 100644 index 0000000..2074543 --- /dev/null +++ b/Opcode/Ice/IceHPoint.cpp @@ -0,0 +1,70 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for homogeneous points. + * \file IceHPoint.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Homogeneous point. + * + * Use it: + * - for clipping in homogeneous space (standard way) + * - to differentiate between points (w=1) and vectors (w=0). + * - in some cases you can also use it instead of IcePoint for padding reasons. + * + * \class HPoint + * \author Pierre Terdiman + * \version 1.0 + * \warning No cross-product in 4D. + * \warning HPoint *= Matrix3x3 doesn't exist, the matrix is first casted to a 4x4 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// IcePoint Mul = HPoint * Matrix3x3; +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +IcePoint HPoint::operator*(const Matrix3x3& mat) const +{ + return IcePoint( + x * mat.m[0][0] + y * mat.m[1][0] + z * mat.m[2][0], + x * mat.m[0][1] + y * mat.m[1][1] + z * mat.m[2][1], + x * mat.m[0][2] + y * mat.m[1][2] + z * mat.m[2][2] ); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// HPoint Mul = HPoint * Matrix4x4; +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +HPoint HPoint::operator*(const Matrix4x4& mat) const +{ + return HPoint( + x * mat.m[0][0] + y * mat.m[1][0] + z * mat.m[2][0] + w * mat.m[3][0], + x * mat.m[0][1] + y * mat.m[1][1] + z * mat.m[2][1] + w * mat.m[3][1], + x * mat.m[0][2] + y * mat.m[1][2] + z * mat.m[2][2] + w * mat.m[3][2], + x * mat.m[0][3] + y * mat.m[1][3] + z * mat.m[2][3] + w * mat.m[3][3]); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// HPoint *= Matrix4x4 +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +HPoint& HPoint::operator*=(const Matrix4x4& mat) +{ + float xp = x * mat.m[0][0] + y * mat.m[1][0] + z * mat.m[2][0] + w * mat.m[3][0]; + float yp = x * mat.m[0][1] + y * mat.m[1][1] + z * mat.m[2][1] + w * mat.m[3][1]; + float zp = x * mat.m[0][2] + y * mat.m[1][2] + z * mat.m[2][2] + w * mat.m[3][2]; + float wp = x * mat.m[0][3] + y * mat.m[1][3] + z * mat.m[2][3] + w * mat.m[3][3]; + + x = xp; y = yp; z = zp; w = wp; + + return *this; +} + diff --git a/Opcode/Ice/IceHPoint.h b/Opcode/Ice/IceHPoint.h new file mode 100644 index 0000000..3065d8e --- /dev/null +++ b/Opcode/Ice/IceHPoint.h @@ -0,0 +1,157 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for homogeneous points. + * \file IceHPoint.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEHPOINT_H__ +#define __ICEHPOINT_H__ + + class ICEMATHS_API HPoint : public Point + { + public: + + //! Empty constructor + inline_ HPoint() {} + //! Constructor from floats + inline_ HPoint(float _x, float _y, float _z, float _w=0.0f) : Point(_x, _y, _z), w(_w) {} + //! Constructor from array + inline_ HPoint(const float f[4]) : Point(f), w(f[3]) {} + //! Constructor from a Point + inline_ HPoint(const Point& p, float _w=0.0f) : Point(p), w(_w) {} + //! Destructor + inline_ ~HPoint() {} + + //! Clear the point + inline_ HPoint& Zero() { x = y = z = w = 0.0f; return *this; } + + //! Assignment from values + inline_ HPoint& Set(float _x, float _y, float _z, float _w ) { x = _x; y = _y; z = _z; w = _w; return *this; } + //! Assignment from array + inline_ HPoint& Set(const float f[4]) { x = f[_X]; y = f[_Y]; z = f[_Z]; w = f[_W]; return *this; } + //! Assignment from another h-point + inline_ HPoint& Set(const HPoint& src) { x = src.x; y = src.y; z = src.z; w = src.w; return *this; } + + //! Add a vector + inline_ HPoint& Add(float _x, float _y, float _z, float _w ) { x += _x; y += _y; z += _z; w += _w; return *this; } + //! Add a vector + inline_ HPoint& Add(const float f[4]) { x += f[_X]; y += f[_Y]; z += f[_Z]; w += f[_W]; return *this; } + + //! Subtract a vector + inline_ HPoint& Sub(float _x, float _y, float _z, float _w ) { x -= _x; y -= _y; z -= _z; w -= _w; return *this; } + //! Subtract a vector + inline_ HPoint& Sub(const float f[4]) { x -= f[_X]; y -= f[_Y]; z -= f[_Z]; w -= f[_W]; return *this; } + + //! Multiplies by a scalar + inline_ HPoint& Mul(float s) { x *= s; y *= s; z *= s; w *= s; return *this; } + + //! Returns MIN(x, y, z, w); + float Min() const { return MIN(x, MIN(y, MIN(z, w))); } + //! Returns MAX(x, y, z, w); + float Max() const { return MAX(x, MAX(y, MAX(z, w))); } + //! Sets each element to be componentwise minimum + HPoint& Min(const HPoint& p) { x = MIN(x, p.x); y = MIN(y, p.y); z = MIN(z, p.z); w = MIN(w, p.w); return *this; } + //! Sets each element to be componentwise maximum + HPoint& Max(const HPoint& p) { x = MAX(x, p.x); y = MAX(y, p.y); z = MAX(z, p.z); w = MAX(w, p.w); return *this; } + + //! Computes square magnitude + inline_ float SquareMagnitude() const { return x*x + y*y + z*z + w*w; } + //! Computes magnitude + inline_ float Magnitude() const { return sqrtf(x*x + y*y + z*z + w*w); } + + //! Normalize the vector + inline_ HPoint& Normalize() + { + float M = Magnitude(); + if(M) + { + M = 1.0f / M; + x *= M; + y *= M; + z *= M; + w *= M; + } + return *this; + } + + // Arithmetic operators + //! Operator for HPoint Negate = - HPoint; + inline_ HPoint operator-() const { return HPoint(-x, -y, -z, -w); } + + //! Operator for HPoint Plus = HPoint + HPoint; + inline_ HPoint operator+(const HPoint& p) const { return HPoint(x + p.x, y + p.y, z + p.z, w + p.w); } + //! Operator for HPoint Minus = HPoint - HPoint; + inline_ HPoint operator-(const HPoint& p) const { return HPoint(x - p.x, y - p.y, z - p.z, w - p.w); } + + //! Operator for HPoint Mul = HPoint * HPoint; + inline_ HPoint operator*(const HPoint& p) const { return HPoint(x * p.x, y * p.y, z * p.z, w * p.w); } + //! Operator for HPoint Scale = HPoint * float; + inline_ HPoint operator*(float s) const { return HPoint(x * s, y * s, z * s, w * s); } + //! Operator for HPoint Scale = float * HPoint; + inline_ friend HPoint operator*(float s, const HPoint& p) { return HPoint(s * p.x, s * p.y, s * p.z, s * p.w); } + + //! Operator for HPoint Div = HPoint / HPoint; + inline_ HPoint operator/(const HPoint& p) const { return HPoint(x / p.x, y / p.y, z / p.z, w / p.w); } + //! Operator for HPoint Scale = HPoint / float; + inline_ HPoint operator/(float s) const { s = 1.0f / s; return HPoint(x * s, y * s, z * s, w * s); } + //! Operator for HPoint Scale = float / HPoint; + inline_ friend HPoint operator/(float s, const HPoint& p) { return HPoint(s / p.x, s / p.y, s / p.z, s / p.w); } + + //! Operator for float DotProd = HPoint | HPoint; + inline_ float operator|(const HPoint& p) const { return x*p.x + y*p.y + z*p.z + w*p.w; } + // No cross-product in 4D + + //! Operator for HPoint += HPoint; + inline_ HPoint& operator+=(const HPoint& p) { x += p.x; y += p.y; z += p.z; w += p.w; return *this; } + //! Operator for HPoint += float; + inline_ HPoint& operator+=(float s) { x += s; y += s; z += s; w += s; return *this; } + + //! Operator for HPoint -= HPoint; + inline_ HPoint& operator-=(const HPoint& p) { x -= p.x; y -= p.y; z -= p.z; w -= p.w; return *this; } + //! Operator for HPoint -= float; + inline_ HPoint& operator-=(float s) { x -= s; y -= s; z -= s; w -= s; return *this; } + + //! Operator for HPoint *= HPoint; + inline_ HPoint& operator*=(const HPoint& p) { x *= p.x; y *= p.y; z *= p.z; w *= p.w; return *this; } + //! Operator for HPoint *= float; + inline_ HPoint& operator*=(float s) { x*=s; y*=s; z*=s; w*=s; return *this; } + + //! Operator for HPoint /= HPoint; + inline_ HPoint& operator/=(const HPoint& p) { x /= p.x; y /= p.y; z /= p.z; w /= p.w; return *this; } + //! Operator for HPoint /= float; + inline_ HPoint& operator/=(float s) { s = 1.0f / s; x*=s; y*=s; z*=s; w*=s; return *this; } + + // Arithmetic operators + + //! Operator for Point Mul = HPoint * Matrix3x3; + Point operator*(const Matrix3x3& mat) const; + //! Operator for HPoint Mul = HPoint * Matrix4x4; + HPoint operator*(const Matrix4x4& mat) const; + + // HPoint *= Matrix3x3 doesn't exist, the matrix is first casted to a 4x4 + //! Operator for HPoint *= Matrix4x4 + HPoint& operator*=(const Matrix4x4& mat); + + // Logical operators + + //! Operator for "if(HPoint==HPoint)" + inline_ bool operator==(const HPoint& p) const { return ( (x==p.x)&&(y==p.y)&&(z==p.z)&&(w==p.w)); } + //! Operator for "if(HPoint!=HPoint)" + inline_ bool operator!=(const HPoint& p) const { return ( (x!=p.x)||(y!=p.y)||(z!=p.z)||(w!=p.w)); } + + // Cast operators + + //! Cast a HPoint to a Point. w is discarded. + inline_ operator Point() const { return Point(x, y, z); } + + public: + float w; + }; + +#endif // __ICEHPOINT_H__ + diff --git a/Opcode/Ice/IceIndexedTriangle.cpp b/Opcode/Ice/IceIndexedTriangle.cpp new file mode 100644 index 0000000..d680f24 --- /dev/null +++ b/Opcode/Ice/IceIndexedTriangle.cpp @@ -0,0 +1,548 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a handy indexed triangle class. + * \file IceIndexedTriangle.cpp + * \author Pierre Terdiman + * \date January, 17, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains an indexed triangle class. + * + * \class Triangle + * \author Pierre Terdiman + * \version 1.0 + * \date 08.15.98 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Flips the winding order. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::Flip() +{ + Swap(mVRef[1], mVRef[2]); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle area. + * \param verts [in] the list of indexed vertices + * \return the area + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::Area(const IcePoint* verts) const +{ + if(!verts) return 0.0f; + const IcePoint& p0 = verts[0]; + const IcePoint& p1 = verts[1]; + const IcePoint& p2 = verts[2]; + return ((p0-p1)^(p0-p2)).Magnitude() * 0.5f; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle perimeter. + * \param verts [in] the list of indexed vertices + * \return the perimeter + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::Perimeter(const IcePoint* verts) const +{ + if(!verts) return 0.0f; + const IcePoint& p0 = verts[0]; + const IcePoint& p1 = verts[1]; + const IcePoint& p2 = verts[2]; + return p0.Distance(p1) + + p0.Distance(p2) + + p1.Distance(p2); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle compacity. + * \param verts [in] the list of indexed vertices + * \return the compacity + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::Compacity(const IcePoint* verts) const +{ + if(!verts) return 0.0f; + float P = Perimeter(verts); + if(P==0.0f) return 0.0f; + return (4.0f*PI*Area(verts)/(P*P)); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle normal. + * \param verts [in] the list of indexed vertices + * \param normal [out] the computed normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::Normal(const IcePoint* verts, IcePoint& normal) const +{ + if(!verts) return; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + normal = ((p2-p1)^(p0-p1)).Normalize(); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle denormalized normal. + * \param verts [in] the list of indexed vertices + * \param normal [out] the computed normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::DenormalizedNormal(const IcePoint* verts, IcePoint& normal) const +{ + if(!verts) return; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + normal = ((p2-p1)^(p0-p1)); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle center. + * \param verts [in] the list of indexed vertices + * \param center [out] the computed center + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::Center(const IcePoint* verts, IcePoint& center) const +{ + if(!verts) return; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + center = (p0+p1+p2)*INV3; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the centered normal + * \param verts [in] the list of indexed vertices + * \param normal [out] the computed centered normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::CenteredNormal(const IcePoint* verts, IcePoint& normal) const +{ + if(!verts) return; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + IcePoint Center = (p0+p1+p2)*INV3; + normal = Center + ((p2-p1)^(p0-p1)).Normalize(); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes a random point within the triangle. + * \param verts [in] the list of indexed vertices + * \param normal [out] the computed centered normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::RandomPoint(const IcePoint* verts, IcePoint& random) const +{ + if(!verts) return; + + // Random barycentric coords + float Alpha = UnitRandomFloat(); + float Beta = UnitRandomFloat(); + float Gamma = UnitRandomFloat(); + float OneOverTotal = 1.0f / (Alpha + Beta + Gamma); + Alpha *= OneOverTotal; + Beta *= OneOverTotal; + Gamma *= OneOverTotal; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + random = Alpha*p0 + Beta*p1 + Gamma*p2; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes backface culling. + * \param verts [in] the list of indexed vertices + * \param source [in] source point (in local space) from which culling must be computed + * \return true if the triangle is visible from the source point + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::IsVisible(const IcePoint* verts, const IcePoint& source) const +{ + // Checkings + if(!verts) return false; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + + // Compute denormalized normal + IcePoint Normal = (p2 - p1)^(p0 - p1); + + // Backface culling + return (Normal | source) >= 0.0f; + +// Same as: +// Plane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]); +// return PL.Distance(source) > PL.d; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes backface culling. + * \param verts [in] the list of indexed vertices + * \param source [in] source point (in local space) from which culling must be computed + * \return true if the triangle is visible from the source point + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::BackfaceCulling(const IcePoint* verts, const IcePoint& source) const +{ + // Checkings + if(!verts) return false; + + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + + // Compute base +// IcePoint Base = (p0 + p1 + p2)*INV3; + + // Compute denormalized normal + IcePoint Normal = (p2 - p1)^(p0 - p1); + + // Backface culling +// return (Normal | (source - Base)) >= 0.0f; + return (Normal | (source - p0)) >= 0.0f; + +// Same as: (but a bit faster) +// Plane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]); +// return PL.Distance(source)>0.0f; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the occlusion potential of the triangle. + * \param verts [in] the list of indexed vertices + * \param source [in] source point (in local space) from which occlusion potential must be computed + * \return the occlusion potential + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::ComputeOcclusionPotential(const IcePoint* verts, const IcePoint& view) const +{ + if(!verts) return 0.0f; + // Occlusion potential: -(A * (N|V) / d^2) + // A = polygon area + // N = polygon normal + // V = view vector + // d = distance viewpoint-center of polygon + + float A = Area(verts); + IcePoint N; Normal(verts, N); + IcePoint C; Center(verts, C); + float d = view.Distance(C); + return -(A*(N|view))/(d*d); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Replaces a vertex reference with another one. + * \param oldref [in] the vertex reference to replace + * \param newref [in] the new vertex reference + * \return true if success, else false if the input vertex reference doesn't belong to the triangle + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::ReplaceVertex(udword oldref, udword newref) +{ + if(mVRef[0]==oldref) { mVRef[0] = newref; return true; } + else if(mVRef[1]==oldref) { mVRef[1] = newref; return true; } + else if(mVRef[2]==oldref) { mVRef[2] = newref; return true; } + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks whether the triangle is degenerate or not. A degenerate triangle has two common vertex references. This is a zero-area triangle. + * \return true if the triangle is degenerate + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::IsDegenerate() const +{ + if(mVRef[0]==mVRef[1]) return true; + if(mVRef[1]==mVRef[2]) return true; + if(mVRef[2]==mVRef[0]) return true; + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks whether the input vertex reference belongs to the triangle or not. + * \param ref [in] the vertex reference to look for + * \return true if the triangle contains the vertex reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::HasVertex(udword ref) const +{ + if(mVRef[0]==ref) return true; + if(mVRef[1]==ref) return true; + if(mVRef[2]==ref) return true; + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks whether the input vertex reference belongs to the triangle or not. + * \param ref [in] the vertex reference to look for + * \param index [out] the corresponding index in the triangle + * \return true if the triangle contains the vertex reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::HasVertex(udword ref, udword* index) const +{ + if(mVRef[0]==ref) { *index = 0; return true; } + if(mVRef[1]==ref) { *index = 1; return true; } + if(mVRef[2]==ref) { *index = 2; return true; } + return false; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Finds an edge in a tri, given two vertex references. + * \param vref0 [in] the edge's first vertex reference + * \param vref1 [in] the edge's second vertex reference + * \return the edge number between 0 and 2, or 0xff if input refs are wrong. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +ubyte IndexedTriangle::FindEdge(udword vref0, udword vref1) const +{ + if(mVRef[0]==vref0 && mVRef[1]==vref1) return 0; + else if(mVRef[0]==vref1 && mVRef[1]==vref0) return 0; + else if(mVRef[0]==vref0 && mVRef[2]==vref1) return 1; + else if(mVRef[0]==vref1 && mVRef[2]==vref0) return 1; + else if(mVRef[1]==vref0 && mVRef[2]==vref1) return 2; + else if(mVRef[1]==vref1 && mVRef[2]==vref0) return 2; + return 0xff; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Gets the last reference given the first two. + * \param vref0 [in] the first vertex reference + * \param vref1 [in] the second vertex reference + * \return the last reference, or INVALID_ID if input refs are wrong. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +udword IndexedTriangle::OppositeVertex(udword vref0, udword vref1) const +{ + if(mVRef[0]==vref0 && mVRef[1]==vref1) return mVRef[2]; + else if(mVRef[0]==vref1 && mVRef[1]==vref0) return mVRef[2]; + else if(mVRef[0]==vref0 && mVRef[2]==vref1) return mVRef[1]; + else if(mVRef[0]==vref1 && mVRef[2]==vref0) return mVRef[1]; + else if(mVRef[1]==vref0 && mVRef[2]==vref1) return mVRef[0]; + else if(mVRef[1]==vref1 && mVRef[2]==vref0) return mVRef[0]; + return INVALID_ID; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Gets the three sorted vertex references according to an edge number. + * edgenb = 0 => edge 0-1, returns references 0, 1, 2 + * edgenb = 1 => edge 0-2, returns references 0, 2, 1 + * edgenb = 2 => edge 1-2, returns references 1, 2, 0 + * + * \param edgenb [in] the edge number, 0, 1 or 2 + * \param vref0 [out] the returned first vertex reference + * \param vref1 [out] the returned second vertex reference + * \param vref2 [out] the returned third vertex reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::GetVRefs(ubyte edgenb, udword& vref0, udword& vref1, udword& vref2) const +{ + if(edgenb==0) + { + vref0 = mVRef[0]; + vref1 = mVRef[1]; + vref2 = mVRef[2]; + } + else if(edgenb==1) + { + vref0 = mVRef[0]; + vref1 = mVRef[2]; + vref2 = mVRef[1]; + } + else if(edgenb==2) + { + vref0 = mVRef[1]; + vref1 = mVRef[2]; + vref2 = mVRef[0]; + } +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle's smallest edge length. + * \param verts [in] the list of indexed vertices + * \return the smallest edge length + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::MinEdgeLength(const IcePoint* verts) const +{ + if(!verts) return 0.0f; + + float Min = MAX_FLOAT; + float Length01 = verts[0].Distance(verts[1]); + float Length02 = verts[0].Distance(verts[2]); + float Length12 = verts[1].Distance(verts[2]); + if(Length01 < Min) Min = Length01; + if(Length02 < Min) Min = Length02; + if(Length12 < Min) Min = Length12; + return Min; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle's largest edge length. + * \param verts [in] the list of indexed vertices + * \return the largest edge length + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::MaxEdgeLength(const IcePoint* verts) const +{ + if(!verts) return 0.0f; + + float Max = MIN_FLOAT; + float Length01 = verts[0].Distance(verts[1]); + float Length02 = verts[0].Distance(verts[2]); + float Length12 = verts[1].Distance(verts[2]); + if(Length01 > Max) Max = Length01; + if(Length02 > Max) Max = Length02; + if(Length12 > Max) Max = Length12; + return Max; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes a point on the triangle according to the stabbing information. + * \param verts [in] the list of indexed vertices + * \param u,v [in] point's barycentric coordinates + * \param pt [out] point on triangle + * \param nearvtx [out] index of nearest vertex + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void IndexedTriangle::ComputePoint(const IcePoint* verts, float u, float v, IcePoint& pt, udword* nearvtx) const +{ + // Checkings + if(!verts) return; + + // Get face in local or global space + const IcePoint& p0 = verts[mVRef[0]]; + const IcePoint& p1 = verts[mVRef[1]]; + const IcePoint& p2 = verts[mVRef[2]]; + + // Compute point coordinates + pt = (1.0f - u - v)*p0 + u*p1 + v*p2; + + // Compute nearest vertex if needed + if(nearvtx) + { + // Compute distance vector + IcePoint d(p0.SquareDistance(pt), // Distance^2 from vertex 0 to point on the face + p1.SquareDistance(pt), // Distance^2 from vertex 1 to point on the face + p2.SquareDistance(pt)); // Distance^2 from vertex 2 to point on the face + + // Get smallest distance + *nearvtx = mVRef[d.SmallestAxis()]; + } +} + + //************************************** + // Angle between two vectors (in radians) + // we use this formula + // uv = |u||v| cos(u,v) + // u ^ v = w + // |w| = |u||v| |sin(u,v)| + //************************************** + float Angle(const IcePoint& u, const IcePoint& v) + { + float NormU = u.Magnitude(); // |u| + float NormV = v.Magnitude(); // |v| + float Product = NormU*NormV; // |u||v| + if(Product==0.0f) return 0.0f; + float OneOverProduct = 1.0f / Product; + + // Cosinus + float Cosinus = (u|v) * OneOverProduct; + + // Sinus + IcePoint w = u^v; + float NormW = w.Magnitude(); + + float AbsSinus = NormW * OneOverProduct; + + // Remove degeneracy + if(AbsSinus > 1.0f) AbsSinus = 1.0f; + if(AbsSinus < -1.0f) AbsSinus = -1.0f; + + if(Cosinus>=0.0f) return asinf(AbsSinus); + else return (PI-asinf(AbsSinus)); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the angle between two triangles. + * \param tri [in] the other triangle + * \param verts [in] the list of indexed vertices + * \return the angle in radians + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float IndexedTriangle::Angle(const IndexedTriangle& tri, const IcePoint* verts) const +{ + // Checkings + if(!verts) return 0.0f; + + // Compute face normals + IcePoint n0, n1; + Normal(verts, n0); + tri.Normal(verts, n1); + + // Compute angle + float dp = n0|n1; + if(dp>1.0f) return 0.0f; + if(dp<-1.0f) return PI; + return acosf(dp); + +// return ::Angle(n0,n1); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks a triangle is the same as another one. + * \param tri [in] the other triangle + * \return true if same triangle + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool IndexedTriangle::Equal(const IndexedTriangle& tri) const +{ + // Test all vertex references + return (HasVertex(tri.mVRef[0]) && + HasVertex(tri.mVRef[1]) && + HasVertex(tri.mVRef[2])); +} diff --git a/Opcode/Ice/IceIndexedTriangle.h b/Opcode/Ice/IceIndexedTriangle.h new file mode 100644 index 0000000..0c497ee --- /dev/null +++ b/Opcode/Ice/IceIndexedTriangle.h @@ -0,0 +1,68 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a handy indexed triangle class. + * \file IceIndexedTriangle.h + * \author Pierre Terdiman + * \date January, 17, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEINDEXEDTRIANGLE_H__ +#define __ICEINDEXEDTRIANGLE_H__ + + // Forward declarations + enum CubeIndex; + + // An indexed triangle class. + class ICEMATHS_API IndexedTriangle + { + public: + //! Constructor + inline_ IndexedTriangle() {} + //! Constructor + inline_ IndexedTriangle(udword r0, udword r1, udword r2) { mVRef[0]=r0; mVRef[1]=r1; mVRef[2]=r2; } + //! Copy constructor + inline_ IndexedTriangle(const IndexedTriangle& triangle) + { + mVRef[0] = triangle.mVRef[0]; + mVRef[1] = triangle.mVRef[1]; + mVRef[2] = triangle.mVRef[2]; + } + //! Destructor + inline_ ~IndexedTriangle() {} + //! Vertex-references + udword mVRef[3]; + + // Methods + void Flip(); + float Area(const Point* verts) const; + float Perimeter(const Point* verts) const; + float Compacity(const Point* verts) const; + void Normal(const Point* verts, Point& normal) const; + void DenormalizedNormal(const Point* verts, Point& normal) const; + void Center(const Point* verts, Point& center) const; + void CenteredNormal(const Point* verts, Point& normal) const; + void RandomPoint(const Point* verts, Point& random) const; + bool IsVisible(const Point* verts, const Point& source) const; + bool BackfaceCulling(const Point* verts, const Point& source) const; + float ComputeOcclusionPotential(const Point* verts, const Point& view) const; + bool ReplaceVertex(udword oldref, udword newref); + bool IsDegenerate() const; + bool HasVertex(udword ref) const; + bool HasVertex(udword ref, udword* index) const; + ubyte FindEdge(udword vref0, udword vref1) const; + udword OppositeVertex(udword vref0, udword vref1) const; + inline_ udword OppositeVertex(ubyte edgenb) const { return mVRef[2-edgenb]; } + void GetVRefs(ubyte edgenb, udword& vref0, udword& vref1, udword& vref2) const; + float MinEdgeLength(const Point* verts) const; + float MaxEdgeLength(const Point* verts) const; + void ComputePoint(const Point* verts, float u, float v, Point& pt, udword* nearvtx=null) const; + float Angle(const IndexedTriangle& tri, const Point* verts) const; + inline_ Plane PlaneEquation(const Point* verts) const { return Plane(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]); } + bool Equal(const IndexedTriangle& tri) const; + CubeIndex ComputeCubeIndex(const Point* verts) const; + }; + +#endif // __ICEINDEXEDTRIANGLE_H__ diff --git a/Opcode/Ice/IceLSS.h b/Opcode/Ice/IceLSS.h new file mode 100644 index 0000000..c16c29f --- /dev/null +++ b/Opcode/Ice/IceLSS.h @@ -0,0 +1,75 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for line-swept spheres. + * \file IceLSS.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICELSS_H__ +#define __ICELSS_H__ + + class ICEMATHS_API LSS : public Segment + { + public: + //! Constructor + inline_ LSS() {} + //! Constructor + inline_ LSS(const Segment& seg, float radius) : Segment(seg), mRadius(radius) {} + //! Destructor + inline_ ~LSS() {} + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes an OBB surrounding the LSS. + * \param box [out] the OBB + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void ComputeOBB(OBB& box); + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a point is contained within the LSS. + * \param pt [in] the point to test + * \return true if inside the LSS + * \warning point and LSS must be in same space + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Contains(const Point& pt) const { return SquareDistance(pt) <= mRadius*mRadius; } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a sphere is contained within the LSS. + * \param sphere [in] the sphere to test + * \return true if inside the LSS + * \warning sphere and LSS must be in same space + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Contains(const Sphere& sphere) + { + float d = mRadius - sphere.mRadius; + if(d>=0.0f) return SquareDistance(sphere.mCenter) <= d*d; + else return false; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if an LSS is contained within the LSS. + * \param lss [in] the LSS to test + * \return true if inside the LSS + * \warning both LSS must be in same space + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ bool Contains(const LSS& lss) + { + // We check the LSS contains the two spheres at the start and end of the sweep + return Contains(Sphere(lss.mP0, lss.mRadius)) && Contains(Sphere(lss.mP0, lss.mRadius)); + } + + float mRadius; //!< Sphere radius + }; + +#endif // __ICELSS_H__ diff --git a/Opcode/Ice/IceMatrix3x3.cpp b/Opcode/Ice/IceMatrix3x3.cpp new file mode 100644 index 0000000..189d39d --- /dev/null +++ b/Opcode/Ice/IceMatrix3x3.cpp @@ -0,0 +1,48 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 3x3 matrices. + * \file IceMatrix3x3.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * 3x3 matrix. + * DirectX-compliant, ie row-column order, ie m[Row][Col]. + * Same as: + * m11 m12 m13 first row. + * m21 m22 m23 second row. + * m31 m32 m33 third row. + * Stored in memory as m11 m12 m13 m21... + * + * Multiplication rules: + * + * [x'y'z'] = [xyz][M] + * + * x' = x*m11 + y*m21 + z*m31 + * y' = x*m12 + y*m22 + z*m32 + * z' = x*m13 + y*m23 + z*m33 + * + * \class Matrix3x3 + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +// Cast operator +Matrix3x3::operator Matrix4x4() const +{ + return Matrix4x4( + m[0][0], m[0][1], m[0][2], 0.0f, + m[1][0], m[1][1], m[1][2], 0.0f, + m[2][0], m[2][1], m[2][2], 0.0f, + 0.0f, 0.0f, 0.0f, 1.0f); +} diff --git a/Opcode/Ice/IceMatrix3x3.h b/Opcode/Ice/IceMatrix3x3.h new file mode 100644 index 0000000..2266fc5 --- /dev/null +++ b/Opcode/Ice/IceMatrix3x3.h @@ -0,0 +1,496 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 3x3 matrices. + * \file IceMatrix3x3.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEMATRIX3X3_H__ +#define __ICEMATRIX3X3_H__ + + // Forward declarations + class Quat; + + #define MATRIX3X3_EPSILON (1.0e-7f) + + class ICEMATHS_API Matrix3x3 + { + public: + //! Empty constructor + inline_ Matrix3x3() {} + //! Constructor from 9 values + inline_ Matrix3x3(float m00, float m01, float m02, float m10, float m11, float m12, float m20, float m21, float m22) + { + m[0][0] = m00; m[0][1] = m01; m[0][2] = m02; + m[1][0] = m10; m[1][1] = m11; m[1][2] = m12; + m[2][0] = m20; m[2][1] = m21; m[2][2] = m22; + } + //! Copy constructor + inline_ Matrix3x3(const Matrix3x3& mat) { CopyMemory(m, &mat.m, 9*sizeof(float)); } + //! Destructor + inline_ ~Matrix3x3() {} + + //! Assign values + inline_ void Set(float m00, float m01, float m02, float m10, float m11, float m12, float m20, float m21, float m22) + { + m[0][0] = m00; m[0][1] = m01; m[0][2] = m02; + m[1][0] = m10; m[1][1] = m11; m[1][2] = m12; + m[2][0] = m20; m[2][1] = m21; m[2][2] = m22; + } + + //! Sets the scale from a Point. The point is put on the diagonal. + inline_ void SetScale(const Point& p) { m[0][0] = p.x; m[1][1] = p.y; m[2][2] = p.z; } + + //! Sets the scale from floats. Values are put on the diagonal. + inline_ void SetScale(float sx, float sy, float sz) { m[0][0] = sx; m[1][1] = sy; m[2][2] = sz; } + + //! Scales from a Point. Each row is multiplied by a component. + inline_ void Scale(const Point& p) + { + m[0][0] *= p.x; m[0][1] *= p.x; m[0][2] *= p.x; + m[1][0] *= p.y; m[1][1] *= p.y; m[1][2] *= p.y; + m[2][0] *= p.z; m[2][1] *= p.z; m[2][2] *= p.z; + } + + //! Scales from floats. Each row is multiplied by a value. + inline_ void Scale(float sx, float sy, float sz) + { + m[0][0] *= sx; m[0][1] *= sx; m[0][2] *= sx; + m[1][0] *= sy; m[1][1] *= sy; m[1][2] *= sy; + m[2][0] *= sz; m[2][1] *= sz; m[2][2] *= sz; + } + + //! Copy from a Matrix3x3 + inline_ void Copy(const Matrix3x3& source) { CopyMemory(m, source.m, 9*sizeof(float)); } + + // Row-column access + //! Returns a row. + inline_ void GetRow(const udword r, Point& p) const { p.x = m[r][0]; p.y = m[r][1]; p.z = m[r][2]; } + //! Returns a row. + inline_ const Point& GetRow(const udword r) const { return *(const Point*)&m[r][0]; } + //! Returns a row. + inline_ Point& GetRow(const udword r) { return *(Point*)&m[r][0]; } + //! Sets a row. + inline_ void SetRow(const udword r, const Point& p) { m[r][0] = p.x; m[r][1] = p.y; m[r][2] = p.z; } + //! Returns a column. + inline_ void GetCol(const udword c, Point& p) const { p.x = m[0][c]; p.y = m[1][c]; p.z = m[2][c]; } + //! Sets a column. + inline_ void SetCol(const udword c, const Point& p) { m[0][c] = p.x; m[1][c] = p.y; m[2][c] = p.z; } + + //! Computes the trace. The trace is the sum of the 3 diagonal components. + inline_ float Trace() const { return m[0][0] + m[1][1] + m[2][2]; } + //! Clears the matrix. + inline_ void Zero() { ZeroMemory(&m, sizeof(m)); } + //! Sets the identity matrix. + inline_ void Identity() { Zero(); m[0][0] = m[1][1] = m[2][2] = 1.0f; } + //! Checks for identity + inline_ bool IsIdentity() const + { + if(IR(m[0][0])!=IEEE_1_0) return false; + if(IR(m[0][1])!=0) return false; + if(IR(m[0][2])!=0) return false; + + if(IR(m[1][0])!=0) return false; + if(IR(m[1][1])!=IEEE_1_0) return false; + if(IR(m[1][2])!=0) return false; + + if(IR(m[2][0])!=0) return false; + if(IR(m[2][1])!=0) return false; + if(IR(m[2][2])!=IEEE_1_0) return false; + + return true; + } + + //! Checks matrix validity + inline_ BOOL IsValid() const + { + for(udword j=0;j<3;j++) + { + for(udword i=0;i<3;i++) + { + if(!IsValidFloat(m[j][i])) return FALSE; + } + } + return TRUE; + } + + //! Makes a skew-symmetric matrix (a.k.a. Star(*) Matrix) + //! [ 0.0 -a.z a.y ] + //! [ a.z 0.0 -a.x ] + //! [ -a.y a.x 0.0 ] + //! This is also called a "cross matrix" since for any vectors A and B, + //! A^B = Skew(A) * B = - B * Skew(A); + inline_ void SkewSymmetric(const Point& a) + { + m[0][0] = 0.0f; + m[0][1] = -a.z; + m[0][2] = a.y; + + m[1][0] = a.z; + m[1][1] = 0.0f; + m[1][2] = -a.x; + + m[2][0] = -a.y; + m[2][1] = a.x; + m[2][2] = 0.0f; + } + + //! Negates the matrix + inline_ void Neg() + { + m[0][0] = -m[0][0]; m[0][1] = -m[0][1]; m[0][2] = -m[0][2]; + m[1][0] = -m[1][0]; m[1][1] = -m[1][1]; m[1][2] = -m[1][2]; + m[2][0] = -m[2][0]; m[2][1] = -m[2][1]; m[2][2] = -m[2][2]; + } + + //! Neg from another matrix + inline_ void Neg(const Matrix3x3& mat) + { + m[0][0] = -mat.m[0][0]; m[0][1] = -mat.m[0][1]; m[0][2] = -mat.m[0][2]; + m[1][0] = -mat.m[1][0]; m[1][1] = -mat.m[1][1]; m[1][2] = -mat.m[1][2]; + m[2][0] = -mat.m[2][0]; m[2][1] = -mat.m[2][1]; m[2][2] = -mat.m[2][2]; + } + + //! Add another matrix + inline_ void Add(const Matrix3x3& mat) + { + m[0][0] += mat.m[0][0]; m[0][1] += mat.m[0][1]; m[0][2] += mat.m[0][2]; + m[1][0] += mat.m[1][0]; m[1][1] += mat.m[1][1]; m[1][2] += mat.m[1][2]; + m[2][0] += mat.m[2][0]; m[2][1] += mat.m[2][1]; m[2][2] += mat.m[2][2]; + } + + //! Sub another matrix + inline_ void Sub(const Matrix3x3& mat) + { + m[0][0] -= mat.m[0][0]; m[0][1] -= mat.m[0][1]; m[0][2] -= mat.m[0][2]; + m[1][0] -= mat.m[1][0]; m[1][1] -= mat.m[1][1]; m[1][2] -= mat.m[1][2]; + m[2][0] -= mat.m[2][0]; m[2][1] -= mat.m[2][1]; m[2][2] -= mat.m[2][2]; + } + //! Mac + inline_ void Mac(const Matrix3x3& a, const Matrix3x3& b, float s) + { + m[0][0] = a.m[0][0] + b.m[0][0] * s; + m[0][1] = a.m[0][1] + b.m[0][1] * s; + m[0][2] = a.m[0][2] + b.m[0][2] * s; + + m[1][0] = a.m[1][0] + b.m[1][0] * s; + m[1][1] = a.m[1][1] + b.m[1][1] * s; + m[1][2] = a.m[1][2] + b.m[1][2] * s; + + m[2][0] = a.m[2][0] + b.m[2][0] * s; + m[2][1] = a.m[2][1] + b.m[2][1] * s; + m[2][2] = a.m[2][2] + b.m[2][2] * s; + } + //! Mac + inline_ void Mac(const Matrix3x3& a, float s) + { + m[0][0] += a.m[0][0] * s; m[0][1] += a.m[0][1] * s; m[0][2] += a.m[0][2] * s; + m[1][0] += a.m[1][0] * s; m[1][1] += a.m[1][1] * s; m[1][2] += a.m[1][2] * s; + m[2][0] += a.m[2][0] * s; m[2][1] += a.m[2][1] * s; m[2][2] += a.m[2][2] * s; + } + + //! this = A * s + inline_ void Mult(const Matrix3x3& a, float s) + { + m[0][0] = a.m[0][0] * s; m[0][1] = a.m[0][1] * s; m[0][2] = a.m[0][2] * s; + m[1][0] = a.m[1][0] * s; m[1][1] = a.m[1][1] * s; m[1][2] = a.m[1][2] * s; + m[2][0] = a.m[2][0] * s; m[2][1] = a.m[2][1] * s; m[2][2] = a.m[2][2] * s; + } + + inline_ void Add(const Matrix3x3& a, const Matrix3x3& b) + { + m[0][0] = a.m[0][0] + b.m[0][0]; m[0][1] = a.m[0][1] + b.m[0][1]; m[0][2] = a.m[0][2] + b.m[0][2]; + m[1][0] = a.m[1][0] + b.m[1][0]; m[1][1] = a.m[1][1] + b.m[1][1]; m[1][2] = a.m[1][2] + b.m[1][2]; + m[2][0] = a.m[2][0] + b.m[2][0]; m[2][1] = a.m[2][1] + b.m[2][1]; m[2][2] = a.m[2][2] + b.m[2][2]; + } + + inline_ void Sub(const Matrix3x3& a, const Matrix3x3& b) + { + m[0][0] = a.m[0][0] - b.m[0][0]; m[0][1] = a.m[0][1] - b.m[0][1]; m[0][2] = a.m[0][2] - b.m[0][2]; + m[1][0] = a.m[1][0] - b.m[1][0]; m[1][1] = a.m[1][1] - b.m[1][1]; m[1][2] = a.m[1][2] - b.m[1][2]; + m[2][0] = a.m[2][0] - b.m[2][0]; m[2][1] = a.m[2][1] - b.m[2][1]; m[2][2] = a.m[2][2] - b.m[2][2]; + } + + //! this = a * b + inline_ void Mult(const Matrix3x3& a, const Matrix3x3& b) + { + m[0][0] = a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[1][0] + a.m[0][2] * b.m[2][0]; + m[0][1] = a.m[0][0] * b.m[0][1] + a.m[0][1] * b.m[1][1] + a.m[0][2] * b.m[2][1]; + m[0][2] = a.m[0][0] * b.m[0][2] + a.m[0][1] * b.m[1][2] + a.m[0][2] * b.m[2][2]; + m[1][0] = a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[1][0] + a.m[1][2] * b.m[2][0]; + m[1][1] = a.m[1][0] * b.m[0][1] + a.m[1][1] * b.m[1][1] + a.m[1][2] * b.m[2][1]; + m[1][2] = a.m[1][0] * b.m[0][2] + a.m[1][1] * b.m[1][2] + a.m[1][2] * b.m[2][2]; + m[2][0] = a.m[2][0] * b.m[0][0] + a.m[2][1] * b.m[1][0] + a.m[2][2] * b.m[2][0]; + m[2][1] = a.m[2][0] * b.m[0][1] + a.m[2][1] * b.m[1][1] + a.m[2][2] * b.m[2][1]; + m[2][2] = a.m[2][0] * b.m[0][2] + a.m[2][1] * b.m[1][2] + a.m[2][2] * b.m[2][2]; + } + + //! this = transpose(a) * b + inline_ void MultAtB(const Matrix3x3& a, const Matrix3x3& b) + { + m[0][0] = a.m[0][0] * b.m[0][0] + a.m[1][0] * b.m[1][0] + a.m[2][0] * b.m[2][0]; + m[0][1] = a.m[0][0] * b.m[0][1] + a.m[1][0] * b.m[1][1] + a.m[2][0] * b.m[2][1]; + m[0][2] = a.m[0][0] * b.m[0][2] + a.m[1][0] * b.m[1][2] + a.m[2][0] * b.m[2][2]; + m[1][0] = a.m[0][1] * b.m[0][0] + a.m[1][1] * b.m[1][0] + a.m[2][1] * b.m[2][0]; + m[1][1] = a.m[0][1] * b.m[0][1] + a.m[1][1] * b.m[1][1] + a.m[2][1] * b.m[2][1]; + m[1][2] = a.m[0][1] * b.m[0][2] + a.m[1][1] * b.m[1][2] + a.m[2][1] * b.m[2][2]; + m[2][0] = a.m[0][2] * b.m[0][0] + a.m[1][2] * b.m[1][0] + a.m[2][2] * b.m[2][0]; + m[2][1] = a.m[0][2] * b.m[0][1] + a.m[1][2] * b.m[1][1] + a.m[2][2] * b.m[2][1]; + m[2][2] = a.m[0][2] * b.m[0][2] + a.m[1][2] * b.m[1][2] + a.m[2][2] * b.m[2][2]; + } + + //! this = a * transpose(b) + inline_ void MultABt(const Matrix3x3& a, const Matrix3x3& b) + { + m[0][0] = a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[0][1] + a.m[0][2] * b.m[0][2]; + m[0][1] = a.m[0][0] * b.m[1][0] + a.m[0][1] * b.m[1][1] + a.m[0][2] * b.m[1][2]; + m[0][2] = a.m[0][0] * b.m[2][0] + a.m[0][1] * b.m[2][1] + a.m[0][2] * b.m[2][2]; + m[1][0] = a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[0][1] + a.m[1][2] * b.m[0][2]; + m[1][1] = a.m[1][0] * b.m[1][0] + a.m[1][1] * b.m[1][1] + a.m[1][2] * b.m[1][2]; + m[1][2] = a.m[1][0] * b.m[2][0] + a.m[1][1] * b.m[2][1] + a.m[1][2] * b.m[2][2]; + m[2][0] = a.m[2][0] * b.m[0][0] + a.m[2][1] * b.m[0][1] + a.m[2][2] * b.m[0][2]; + m[2][1] = a.m[2][0] * b.m[1][0] + a.m[2][1] * b.m[1][1] + a.m[2][2] * b.m[1][2]; + m[2][2] = a.m[2][0] * b.m[2][0] + a.m[2][1] * b.m[2][1] + a.m[2][2] * b.m[2][2]; + } + + //! Makes a rotation matrix mapping vector "from" to vector "to". + Matrix3x3& FromTo(const Point& from, const Point& to); + + //! Set a rotation matrix around the X axis. + //! 1 0 0 + //! RX = 0 cx sx + //! 0 -sx cx + void RotX(float angle); + //! Set a rotation matrix around the Y axis. + //! cy 0 -sy + //! RY = 0 1 0 + //! sy 0 cy + void RotY(float angle); + //! Set a rotation matrix around the Z axis. + //! cz sz 0 + //! RZ = -sz cz 0 + //! 0 0 1 + void RotZ(float angle); + //! cy sx.sy -sy.cx + //! RY.RX 0 cx sx + //! sy -sx.cy cx.cy + void RotYX(float y, float x); + + //! Make a rotation matrix about an arbitrary axis + Matrix3x3& Rot(float angle, const Point& axis); + + //! Transpose the matrix. + void Transpose() + { + IR(m[1][0]) ^= IR(m[0][1]); IR(m[0][1]) ^= IR(m[1][0]); IR(m[1][0]) ^= IR(m[0][1]); + IR(m[2][0]) ^= IR(m[0][2]); IR(m[0][2]) ^= IR(m[2][0]); IR(m[2][0]) ^= IR(m[0][2]); + IR(m[2][1]) ^= IR(m[1][2]); IR(m[1][2]) ^= IR(m[2][1]); IR(m[2][1]) ^= IR(m[1][2]); + } + + //! this = Transpose(a) + void Transpose(const Matrix3x3& a) + { + m[0][0] = a.m[0][0]; m[0][1] = a.m[1][0]; m[0][2] = a.m[2][0]; + m[1][0] = a.m[0][1]; m[1][1] = a.m[1][1]; m[1][2] = a.m[2][1]; + m[2][0] = a.m[0][2]; m[2][1] = a.m[1][2]; m[2][2] = a.m[2][2]; + } + + //! Compute the determinant of the matrix. We use the rule of Sarrus. + float Determinant() const + { + return (m[0][0]*m[1][1]*m[2][2] + m[0][1]*m[1][2]*m[2][0] + m[0][2]*m[1][0]*m[2][1]) + - (m[2][0]*m[1][1]*m[0][2] + m[2][1]*m[1][2]*m[0][0] + m[2][2]*m[1][0]*m[0][1]); + } +/* + //! Compute a cofactor. Used for matrix inversion. + float CoFactor(ubyte row, ubyte column) const + { + static sdword gIndex[3+2] = { 0, 1, 2, 0, 1 }; + return (m[gIndex[row+1]][gIndex[column+1]]*m[gIndex[row+2]][gIndex[column+2]] - m[gIndex[row+2]][gIndex[column+1]]*m[gIndex[row+1]][gIndex[column+2]]); + } +*/ + //! Invert the matrix. Determinant must be different from zero, else matrix can't be inverted. + Matrix3x3& Invert() + { + float Det = Determinant(); // Must be !=0 + float OneOverDet = 1.0f / Det; + + Matrix3x3 Temp; + Temp.m[0][0] = +(m[1][1] * m[2][2] - m[2][1] * m[1][2]) * OneOverDet; + Temp.m[1][0] = -(m[1][0] * m[2][2] - m[2][0] * m[1][2]) * OneOverDet; + Temp.m[2][0] = +(m[1][0] * m[2][1] - m[2][0] * m[1][1]) * OneOverDet; + Temp.m[0][1] = -(m[0][1] * m[2][2] - m[2][1] * m[0][2]) * OneOverDet; + Temp.m[1][1] = +(m[0][0] * m[2][2] - m[2][0] * m[0][2]) * OneOverDet; + Temp.m[2][1] = -(m[0][0] * m[2][1] - m[2][0] * m[0][1]) * OneOverDet; + Temp.m[0][2] = +(m[0][1] * m[1][2] - m[1][1] * m[0][2]) * OneOverDet; + Temp.m[1][2] = -(m[0][0] * m[1][2] - m[1][0] * m[0][2]) * OneOverDet; + Temp.m[2][2] = +(m[0][0] * m[1][1] - m[1][0] * m[0][1]) * OneOverDet; + + *this = Temp; + + return *this; + } + + Matrix3x3& Normalize(); + + //! this = exp(a) + Matrix3x3& Exp(const Matrix3x3& a); + +void FromQuat(const Quat &q); +void FromQuatL2(const Quat &q, float l2); + + // Arithmetic operators + //! Operator for Matrix3x3 Plus = Matrix3x3 + Matrix3x3; + inline_ Matrix3x3 operator+(const Matrix3x3& mat) const + { + return Matrix3x3( + m[0][0] + mat.m[0][0], m[0][1] + mat.m[0][1], m[0][2] + mat.m[0][2], + m[1][0] + mat.m[1][0], m[1][1] + mat.m[1][1], m[1][2] + mat.m[1][2], + m[2][0] + mat.m[2][0], m[2][1] + mat.m[2][1], m[2][2] + mat.m[2][2]); + } + + //! Operator for Matrix3x3 Minus = Matrix3x3 - Matrix3x3; + inline_ Matrix3x3 operator-(const Matrix3x3& mat) const + { + return Matrix3x3( + m[0][0] - mat.m[0][0], m[0][1] - mat.m[0][1], m[0][2] - mat.m[0][2], + m[1][0] - mat.m[1][0], m[1][1] - mat.m[1][1], m[1][2] - mat.m[1][2], + m[2][0] - mat.m[2][0], m[2][1] - mat.m[2][1], m[2][2] - mat.m[2][2]); + } + + //! Operator for Matrix3x3 Mul = Matrix3x3 * Matrix3x3; + inline_ Matrix3x3 operator*(const Matrix3x3& mat) const + { + return Matrix3x3( + m[0][0]*mat.m[0][0] + m[0][1]*mat.m[1][0] + m[0][2]*mat.m[2][0], + m[0][0]*mat.m[0][1] + m[0][1]*mat.m[1][1] + m[0][2]*mat.m[2][1], + m[0][0]*mat.m[0][2] + m[0][1]*mat.m[1][2] + m[0][2]*mat.m[2][2], + + m[1][0]*mat.m[0][0] + m[1][1]*mat.m[1][0] + m[1][2]*mat.m[2][0], + m[1][0]*mat.m[0][1] + m[1][1]*mat.m[1][1] + m[1][2]*mat.m[2][1], + m[1][0]*mat.m[0][2] + m[1][1]*mat.m[1][2] + m[1][2]*mat.m[2][2], + + m[2][0]*mat.m[0][0] + m[2][1]*mat.m[1][0] + m[2][2]*mat.m[2][0], + m[2][0]*mat.m[0][1] + m[2][1]*mat.m[1][1] + m[2][2]*mat.m[2][1], + m[2][0]*mat.m[0][2] + m[2][1]*mat.m[1][2] + m[2][2]*mat.m[2][2]); + } + + //! Operator for Point Mul = Matrix3x3 * Point; + inline_ Point operator*(const Point& v) const { return Point(GetRow(0)|v, GetRow(1)|v, GetRow(2)|v); } + + //! Operator for Matrix3x3 Mul = Matrix3x3 * float; + inline_ Matrix3x3 operator*(float s) const + { + return Matrix3x3( + m[0][0]*s, m[0][1]*s, m[0][2]*s, + m[1][0]*s, m[1][1]*s, m[1][2]*s, + m[2][0]*s, m[2][1]*s, m[2][2]*s); + } + + //! Operator for Matrix3x3 Mul = float * Matrix3x3; + inline_ friend Matrix3x3 operator*(float s, const Matrix3x3& mat) + { + return Matrix3x3( + s*mat.m[0][0], s*mat.m[0][1], s*mat.m[0][2], + s*mat.m[1][0], s*mat.m[1][1], s*mat.m[1][2], + s*mat.m[2][0], s*mat.m[2][1], s*mat.m[2][2]); + } + + //! Operator for Matrix3x3 Div = Matrix3x3 / float; + inline_ Matrix3x3 operator/(float s) const + { + if (s) s = 1.0f / s; + return Matrix3x3( + m[0][0]*s, m[0][1]*s, m[0][2]*s, + m[1][0]*s, m[1][1]*s, m[1][2]*s, + m[2][0]*s, m[2][1]*s, m[2][2]*s); + } + + //! Operator for Matrix3x3 Div = float / Matrix3x3; + inline_ friend Matrix3x3 operator/(float s, const Matrix3x3& mat) + { + return Matrix3x3( + s/mat.m[0][0], s/mat.m[0][1], s/mat.m[0][2], + s/mat.m[1][0], s/mat.m[1][1], s/mat.m[1][2], + s/mat.m[2][0], s/mat.m[2][1], s/mat.m[2][2]); + } + + //! Operator for Matrix3x3 += Matrix3x3 + inline_ Matrix3x3& operator+=(const Matrix3x3& mat) + { + m[0][0] += mat.m[0][0]; m[0][1] += mat.m[0][1]; m[0][2] += mat.m[0][2]; + m[1][0] += mat.m[1][0]; m[1][1] += mat.m[1][1]; m[1][2] += mat.m[1][2]; + m[2][0] += mat.m[2][0]; m[2][1] += mat.m[2][1]; m[2][2] += mat.m[2][2]; + return *this; + } + + //! Operator for Matrix3x3 -= Matrix3x3 + inline_ Matrix3x3& operator-=(const Matrix3x3& mat) + { + m[0][0] -= mat.m[0][0]; m[0][1] -= mat.m[0][1]; m[0][2] -= mat.m[0][2]; + m[1][0] -= mat.m[1][0]; m[1][1] -= mat.m[1][1]; m[1][2] -= mat.m[1][2]; + m[2][0] -= mat.m[2][0]; m[2][1] -= mat.m[2][1]; m[2][2] -= mat.m[2][2]; + return *this; + } + + //! Operator for Matrix3x3 *= Matrix3x3 + inline_ Matrix3x3& operator*=(const Matrix3x3& mat) + { + Point TempRow; + + GetRow(0, TempRow); + m[0][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0]; + m[0][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1]; + m[0][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2]; + + GetRow(1, TempRow); + m[1][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0]; + m[1][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1]; + m[1][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2]; + + GetRow(2, TempRow); + m[2][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0]; + m[2][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1]; + m[2][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2]; + return *this; + } + + //! Operator for Matrix3x3 *= float + inline_ Matrix3x3& operator*=(float s) + { + m[0][0] *= s; m[0][1] *= s; m[0][2] *= s; + m[1][0] *= s; m[1][1] *= s; m[1][2] *= s; + m[2][0] *= s; m[2][1] *= s; m[2][2] *= s; + return *this; + } + + //! Operator for Matrix3x3 /= float + inline_ Matrix3x3& operator/=(float s) + { + if (s) s = 1.0f / s; + m[0][0] *= s; m[0][1] *= s; m[0][2] *= s; + m[1][0] *= s; m[1][1] *= s; m[1][2] *= s; + m[2][0] *= s; m[2][1] *= s; m[2][2] *= s; + return *this; + } + + // Cast operators + //! Cast a Matrix3x3 to a Matrix4x4. + operator Matrix4x4() const; + //! Cast a Matrix3x3 to a Quat. + operator Quat() const; + + inline_ const Point& operator[](int row) const { return *(const Point*)&m[row][0]; } + inline_ Point& operator[](int row) { return *(Point*)&m[row][0]; } + + public: + + float m[3][3]; + }; + +#endif // __ICEMATRIX3X3_H__ + diff --git a/Opcode/Ice/IceMatrix4x4.cpp b/Opcode/Ice/IceMatrix4x4.cpp new file mode 100644 index 0000000..4c539c9 --- /dev/null +++ b/Opcode/Ice/IceMatrix4x4.cpp @@ -0,0 +1,135 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 4x4 matrices. + * \file IceMatrix4x4.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * 4x4 matrix. + * DirectX-compliant, ie row-column order, ie m[Row][Col]. + * Same as: + * m11 m12 m13 m14 first row. + * m21 m22 m23 m24 second row. + * m31 m32 m33 m34 third row. + * m41 m42 m43 m44 fourth row. + * Translation is (m41, m42, m43), (m14, m24, m34, m44) = (0, 0, 0, 1). + * Stored in memory as m11 m12 m13 m14 m21... + * + * Multiplication rules: + * + * [x'y'z'1] = [xyz1][M] + * + * x' = x*m11 + y*m21 + z*m31 + m41 + * y' = x*m12 + y*m22 + z*m32 + m42 + * z' = x*m13 + y*m23 + z*m33 + m43 + * 1' = 0 + 0 + 0 + m44 + * + * \class Matrix4x4 + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Inverts a PR matrix. (which only contains a rotation and a translation) + * This is faster and less subject to FPU errors than the generic inversion code. + * + * \relates Matrix4x4 + * \fn InvertPRMatrix(Matrix4x4& dest, const Matrix4x4& src) + * \param dest [out] destination matrix + * \param src [in] source matrix + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +ICEMATHS_API void IceMaths::InvertPRMatrix(Matrix4x4& dest, const Matrix4x4& src) +{ + dest.m[0][0] = src.m[0][0]; + dest.m[1][0] = src.m[0][1]; + dest.m[2][0] = src.m[0][2]; + dest.m[3][0] = -(src.m[3][0]*src.m[0][0] + src.m[3][1]*src.m[0][1] + src.m[3][2]*src.m[0][2]); + + dest.m[0][1] = src.m[1][0]; + dest.m[1][1] = src.m[1][1]; + dest.m[2][1] = src.m[1][2]; + dest.m[3][1] = -(src.m[3][0]*src.m[1][0] + src.m[3][1]*src.m[1][1] + src.m[3][2]*src.m[1][2]); + + dest.m[0][2] = src.m[2][0]; + dest.m[1][2] = src.m[2][1]; + dest.m[2][2] = src.m[2][2]; + dest.m[3][2] = -(src.m[3][0]*src.m[2][0] + src.m[3][1]*src.m[2][1] + src.m[3][2]*src.m[2][2]); + + dest.m[0][3] = 0.0f; + dest.m[1][3] = 0.0f; + dest.m[2][3] = 0.0f; + dest.m[3][3] = 1.0f; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Compute the cofactor of the Matrix at a specified location +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Matrix4x4::CoFactor(udword row, udword col) const +{ + return (( m[(row+1)&3][(col+1)&3]*m[(row+2)&3][(col+2)&3]*m[(row+3)&3][(col+3)&3] + + m[(row+1)&3][(col+2)&3]*m[(row+2)&3][(col+3)&3]*m[(row+3)&3][(col+1)&3] + + m[(row+1)&3][(col+3)&3]*m[(row+2)&3][(col+1)&3]*m[(row+3)&3][(col+2)&3]) + - (m[(row+3)&3][(col+1)&3]*m[(row+2)&3][(col+2)&3]*m[(row+1)&3][(col+3)&3] + + m[(row+3)&3][(col+2)&3]*m[(row+2)&3][(col+3)&3]*m[(row+1)&3][(col+1)&3] + + m[(row+3)&3][(col+3)&3]*m[(row+2)&3][(col+1)&3]*m[(row+1)&3][(col+2)&3])) * ((row + col) & 1 ? -1.0f : +1.0f); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Compute the determinant of the Matrix +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Matrix4x4::Determinant() const +{ + return m[0][0] * CoFactor(0, 0) + + m[0][1] * CoFactor(0, 1) + + m[0][2] * CoFactor(0, 2) + + m[0][3] * CoFactor(0, 3); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Compute the inverse of the matrix +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Matrix4x4& Matrix4x4::Invert() +{ + float Det = Determinant(); + Matrix4x4 Temp; + + if(fabsf(Det) < MATRIX4X4_EPSILON) + return *this; // The matrix is not invertible! Singular case! + + float IDet = 1.0f / Det; + + Temp.m[0][0] = CoFactor(0,0) * IDet; + Temp.m[1][0] = CoFactor(0,1) * IDet; + Temp.m[2][0] = CoFactor(0,2) * IDet; + Temp.m[3][0] = CoFactor(0,3) * IDet; + Temp.m[0][1] = CoFactor(1,0) * IDet; + Temp.m[1][1] = CoFactor(1,1) * IDet; + Temp.m[2][1] = CoFactor(1,2) * IDet; + Temp.m[3][1] = CoFactor(1,3) * IDet; + Temp.m[0][2] = CoFactor(2,0) * IDet; + Temp.m[1][2] = CoFactor(2,1) * IDet; + Temp.m[2][2] = CoFactor(2,2) * IDet; + Temp.m[3][2] = CoFactor(2,3) * IDet; + Temp.m[0][3] = CoFactor(3,0) * IDet; + Temp.m[1][3] = CoFactor(3,1) * IDet; + Temp.m[2][3] = CoFactor(3,2) * IDet; + Temp.m[3][3] = CoFactor(3,3) * IDet; + + *this = Temp; + + return *this; +} + diff --git a/Opcode/Ice/IceMatrix4x4.h b/Opcode/Ice/IceMatrix4x4.h new file mode 100644 index 0000000..d61a461 --- /dev/null +++ b/Opcode/Ice/IceMatrix4x4.h @@ -0,0 +1,455 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 4x4 matrices. + * \file IceMatrix4x4.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEMATRIX4X4_H__ +#define __ICEMATRIX4X4_H__ + + // Forward declarations + class PRS; + class PR; + + #define MATRIX4X4_EPSILON (1.0e-7f) + + class ICEMATHS_API Matrix4x4 + { +// void LUBackwardSubstitution( sdword *indx, float* b ); +// void LUDecomposition( sdword* indx, float* d ); + + public: + //! Empty constructor. + inline_ Matrix4x4() {} + //! Constructor from 16 values + inline_ Matrix4x4( float m00, float m01, float m02, float m03, + float m10, float m11, float m12, float m13, + float m20, float m21, float m22, float m23, + float m30, float m31, float m32, float m33) + { + m[0][0] = m00; m[0][1] = m01; m[0][2] = m02; m[0][3] = m03; + m[1][0] = m10; m[1][1] = m11; m[1][2] = m12; m[1][3] = m13; + m[2][0] = m20; m[2][1] = m21; m[2][2] = m22; m[2][3] = m23; + m[3][0] = m30; m[3][1] = m31; m[3][2] = m32; m[3][3] = m33; + } + //! Copy constructor + inline_ Matrix4x4(const Matrix4x4& mat) { CopyMemory(m, &mat.m, 16*sizeof(float)); } + //! Destructor. + inline_ ~Matrix4x4() {} + + //! Assign values (rotation only) + inline_ Matrix4x4& Set( float m00, float m01, float m02, + float m10, float m11, float m12, + float m20, float m21, float m22) + { + m[0][0] = m00; m[0][1] = m01; m[0][2] = m02; + m[1][0] = m10; m[1][1] = m11; m[1][2] = m12; + m[2][0] = m20; m[2][1] = m21; m[2][2] = m22; + return *this; + } + //! Assign values + inline_ Matrix4x4& Set( float m00, float m01, float m02, float m03, + float m10, float m11, float m12, float m13, + float m20, float m21, float m22, float m23, + float m30, float m31, float m32, float m33) + { + m[0][0] = m00; m[0][1] = m01; m[0][2] = m02; m[0][3] = m03; + m[1][0] = m10; m[1][1] = m11; m[1][2] = m12; m[1][3] = m13; + m[2][0] = m20; m[2][1] = m21; m[2][2] = m22; m[2][3] = m23; + m[3][0] = m30; m[3][1] = m31; m[3][2] = m32; m[3][3] = m33; + return *this; + } + + //! Copy from a Matrix4x4 + inline_ void Copy(const Matrix4x4& source) { CopyMemory(m, source.m, 16*sizeof(float)); } + + // Row-column access + //! Returns a row. + inline_ void GetRow(const udword r, HPoint& p) const { p.x=m[r][0]; p.y=m[r][1]; p.z=m[r][2]; p.w=m[r][3]; } + //! Returns a row. + inline_ void GetRow(const udword r, Point& p) const { p.x=m[r][0]; p.y=m[r][1]; p.z=m[r][2]; } + //! Returns a row. + inline_ const HPoint& GetRow(const udword r) const { return *(const HPoint*)&m[r][0]; } + //! Returns a row. + inline_ HPoint& GetRow(const udword r) { return *(HPoint*)&m[r][0]; } + //! Sets a row. + inline_ void SetRow(const udword r, const HPoint& p) { m[r][0]=p.x; m[r][1]=p.y; m[r][2]=p.z; m[r][3]=p.w; } + //! Sets a row. + inline_ void SetRow(const udword r, const Point& p) { m[r][0]=p.x; m[r][1]=p.y; m[r][2]=p.z; m[r][3]= (r!=3) ? 0.0f : 1.0f; } + //! Returns a column. + inline_ void GetCol(const udword c, HPoint& p) const { p.x=m[0][c]; p.y=m[1][c]; p.z=m[2][c]; p.w=m[3][c]; } + //! Returns a column. + inline_ void GetCol(const udword c, Point& p) const { p.x=m[0][c]; p.y=m[1][c]; p.z=m[2][c]; } + //! Sets a column. + inline_ void SetCol(const udword c, const HPoint& p) { m[0][c]=p.x; m[1][c]=p.y; m[2][c]=p.z; m[3][c]=p.w; } + //! Sets a column. + inline_ void SetCol(const udword c, const Point& p) { m[0][c]=p.x; m[1][c]=p.y; m[2][c]=p.z; m[3][c]= (c!=3) ? 0.0f : 1.0f; } + + // Translation + //! Returns the translation part of the matrix. + inline_ const HPoint& GetTrans() const { return GetRow(3); } + //! Gets the translation part of the matrix + inline_ void GetTrans(Point& p) const { p.x=m[3][0]; p.y=m[3][1]; p.z=m[3][2]; } + //! Sets the translation part of the matrix, from a Point. + inline_ void SetTrans(const Point& p) { m[3][0]=p.x; m[3][1]=p.y; m[3][2]=p.z; } + //! Sets the translation part of the matrix, from a HPoint. + inline_ void SetTrans(const HPoint& p) { m[3][0]=p.x; m[3][1]=p.y; m[3][2]=p.z; m[3][3]=p.w; } + //! Sets the translation part of the matrix, from floats. + inline_ void SetTrans(float tx, float ty, float tz) { m[3][0]=tx; m[3][1]=ty; m[3][2]=tz; } + + // Scale + //! Sets the scale from a Point. The point is put on the diagonal. + inline_ void SetScale(const Point& p) { m[0][0]=p.x; m[1][1]=p.y; m[2][2]=p.z; } + //! Sets the scale from floats. Values are put on the diagonal. + inline_ void SetScale(float sx, float sy, float sz) { m[0][0]=sx; m[1][1]=sy; m[2][2]=sz; } + //! Scales from a Point. Each row is multiplied by a component. + void Scale(const Point& p) + { + m[0][0] *= p.x; m[1][0] *= p.y; m[2][0] *= p.z; + m[0][1] *= p.x; m[1][1] *= p.y; m[2][1] *= p.z; + m[0][2] *= p.x; m[1][2] *= p.y; m[2][2] *= p.z; + } + //! Scales from floats. Each row is multiplied by a value. + void Scale(float sx, float sy, float sz) + { + m[0][0] *= sx; m[1][0] *= sy; m[2][0] *= sz; + m[0][1] *= sx; m[1][1] *= sy; m[2][1] *= sz; + m[0][2] *= sx; m[1][2] *= sy; m[2][2] *= sz; + } +/* + //! Returns a row. + inline_ HPoint GetRow(const udword row) const { return mRow[row]; } + //! Sets a row. + inline_ Matrix4x4& SetRow(const udword row, const HPoint& p) { mRow[row] = p; return *this; } + //! Sets a row. + Matrix4x4& SetRow(const udword row, const Point& p) + { + m[row][0] = p.x; + m[row][1] = p.y; + m[row][2] = p.z; + m[row][3] = (row != 3) ? 0.0f : 1.0f; + return *this; + } + //! Returns a column. + HPoint GetCol(const udword col) const + { + HPoint Res; + Res.x = m[0][col]; + Res.y = m[1][col]; + Res.z = m[2][col]; + Res.w = m[3][col]; + return Res; + } + //! Sets a column. + Matrix4x4& SetCol(const udword col, const HPoint& p) + { + m[0][col] = p.x; + m[1][col] = p.y; + m[2][col] = p.z; + m[3][col] = p.w; + return *this; + } + //! Sets a column. + Matrix4x4& SetCol(const udword col, const Point& p) + { + m[0][col] = p.x; + m[1][col] = p.y; + m[2][col] = p.z; + m[3][col] = (col != 3) ? 0.0f : 1.0f; + return *this; + } +*/ + //! Computes the trace. The trace is the sum of the 4 diagonal components. + inline_ float Trace() const { return m[0][0] + m[1][1] + m[2][2] + m[3][3]; } + //! Computes the trace of the upper 3x3 matrix. + inline_ float Trace3x3() const { return m[0][0] + m[1][1] + m[2][2]; } + //! Clears the matrix. + inline_ void Zero() { ZeroMemory(&m, sizeof(m)); } + //! Sets the identity matrix. + inline_ void Identity() { Zero(); m[0][0] = m[1][1] = m[2][2] = m[3][3] = 1.0f; } + //! Checks for identity + inline_ bool IsIdentity() const + { + if(IR(m[0][0])!=IEEE_1_0) return false; + if(IR(m[0][1])!=0) return false; + if(IR(m[0][2])!=0) return false; + if(IR(m[0][3])!=0) return false; + + if(IR(m[1][0])!=0) return false; + if(IR(m[1][1])!=IEEE_1_0) return false; + if(IR(m[1][2])!=0) return false; + if(IR(m[1][3])!=0) return false; + + if(IR(m[2][0])!=0) return false; + if(IR(m[2][1])!=0) return false; + if(IR(m[2][2])!=IEEE_1_0) return false; + if(IR(m[2][3])!=0) return false; + + if(IR(m[3][0])!=0) return false; + if(IR(m[3][1])!=0) return false; + if(IR(m[3][2])!=0) return false; + if(IR(m[3][3])!=IEEE_1_0) return false; + return true; + } + + //! Checks matrix validity + inline_ BOOL IsValid() const + { + for(udword j=0;j<4;j++) + { + for(udword i=0;i<4;i++) + { + if(!IsValidFloat(m[j][i])) return FALSE; + } + } + return TRUE; + } + + //! Sets a rotation matrix around the X axis. + void RotX(float angle) { float Cos = cosf(angle), Sin = sinf(angle); Identity(); m[1][1] = m[2][2] = Cos; m[2][1] = -Sin; m[1][2] = Sin; } + //! Sets a rotation matrix around the Y axis. + void RotY(float angle) { float Cos = cosf(angle), Sin = sinf(angle); Identity(); m[0][0] = m[2][2] = Cos; m[2][0] = Sin; m[0][2] = -Sin; } + //! Sets a rotation matrix around the Z axis. + void RotZ(float angle) { float Cos = cosf(angle), Sin = sinf(angle); Identity(); m[0][0] = m[1][1] = Cos; m[1][0] = -Sin; m[0][1] = Sin; } + + //! Makes a rotation matrix about an arbitrary axis + Matrix4x4& Rot(float angle, Point& p1, Point& p2); + + //! Transposes the matrix. + void Transpose() + { + IR(m[1][0]) ^= IR(m[0][1]); IR(m[0][1]) ^= IR(m[1][0]); IR(m[1][0]) ^= IR(m[0][1]); + IR(m[2][0]) ^= IR(m[0][2]); IR(m[0][2]) ^= IR(m[2][0]); IR(m[2][0]) ^= IR(m[0][2]); + IR(m[3][0]) ^= IR(m[0][3]); IR(m[0][3]) ^= IR(m[3][0]); IR(m[3][0]) ^= IR(m[0][3]); + IR(m[1][2]) ^= IR(m[2][1]); IR(m[2][1]) ^= IR(m[1][2]); IR(m[1][2]) ^= IR(m[2][1]); + IR(m[1][3]) ^= IR(m[3][1]); IR(m[3][1]) ^= IR(m[1][3]); IR(m[1][3]) ^= IR(m[3][1]); + IR(m[2][3]) ^= IR(m[3][2]); IR(m[3][2]) ^= IR(m[2][3]); IR(m[2][3]) ^= IR(m[3][2]); + } + + //! Computes a cofactor. Used for matrix inversion. + float CoFactor(udword row, udword col) const; + //! Computes the determinant of the matrix. + float Determinant() const; + //! Inverts the matrix. Determinant must be different from zero, else matrix can't be inverted. + Matrix4x4& Invert(); +// Matrix& ComputeAxisMatrix(Point& axis, float angle); + + // Cast operators + //! Casts a Matrix4x4 to a Matrix3x3. + inline_ operator Matrix3x3() const + { + return Matrix3x3( + m[0][0], m[0][1], m[0][2], + m[1][0], m[1][1], m[1][2], + m[2][0], m[2][1], m[2][2]); + } + //! Casts a Matrix4x4 to a Quat. + operator Quat() const; + //! Casts a Matrix4x4 to a PR. + operator PR() const; + + // Arithmetic operators + //! Operator for Matrix4x4 Plus = Matrix4x4 + Matrix4x4; + inline_ Matrix4x4 operator+(const Matrix4x4& mat) const + { + return Matrix4x4( + m[0][0]+mat.m[0][0], m[0][1]+mat.m[0][1], m[0][2]+mat.m[0][2], m[0][3]+mat.m[0][3], + m[1][0]+mat.m[1][0], m[1][1]+mat.m[1][1], m[1][2]+mat.m[1][2], m[1][3]+mat.m[1][3], + m[2][0]+mat.m[2][0], m[2][1]+mat.m[2][1], m[2][2]+mat.m[2][2], m[2][3]+mat.m[2][3], + m[3][0]+mat.m[3][0], m[3][1]+mat.m[3][1], m[3][2]+mat.m[3][2], m[3][3]+mat.m[3][3]); + } + + //! Operator for Matrix4x4 Minus = Matrix4x4 - Matrix4x4; + inline_ Matrix4x4 operator-(const Matrix4x4& mat) const + { + return Matrix4x4( + m[0][0]-mat.m[0][0], m[0][1]-mat.m[0][1], m[0][2]-mat.m[0][2], m[0][3]-mat.m[0][3], + m[1][0]-mat.m[1][0], m[1][1]-mat.m[1][1], m[1][2]-mat.m[1][2], m[1][3]-mat.m[1][3], + m[2][0]-mat.m[2][0], m[2][1]-mat.m[2][1], m[2][2]-mat.m[2][2], m[2][3]-mat.m[2][3], + m[3][0]-mat.m[3][0], m[3][1]-mat.m[3][1], m[3][2]-mat.m[3][2], m[3][3]-mat.m[3][3]); + } + + //! Operator for Matrix4x4 Mul = Matrix4x4 * Matrix4x4; + inline_ Matrix4x4 operator*(const Matrix4x4& mat) const + { + return Matrix4x4( + m[0][0]*mat.m[0][0] + m[0][1]*mat.m[1][0] + m[0][2]*mat.m[2][0] + m[0][3]*mat.m[3][0], + m[0][0]*mat.m[0][1] + m[0][1]*mat.m[1][1] + m[0][2]*mat.m[2][1] + m[0][3]*mat.m[3][1], + m[0][0]*mat.m[0][2] + m[0][1]*mat.m[1][2] + m[0][2]*mat.m[2][2] + m[0][3]*mat.m[3][2], + m[0][0]*mat.m[0][3] + m[0][1]*mat.m[1][3] + m[0][2]*mat.m[2][3] + m[0][3]*mat.m[3][3], + + m[1][0]*mat.m[0][0] + m[1][1]*mat.m[1][0] + m[1][2]*mat.m[2][0] + m[1][3]*mat.m[3][0], + m[1][0]*mat.m[0][1] + m[1][1]*mat.m[1][1] + m[1][2]*mat.m[2][1] + m[1][3]*mat.m[3][1], + m[1][0]*mat.m[0][2] + m[1][1]*mat.m[1][2] + m[1][2]*mat.m[2][2] + m[1][3]*mat.m[3][2], + m[1][0]*mat.m[0][3] + m[1][1]*mat.m[1][3] + m[1][2]*mat.m[2][3] + m[1][3]*mat.m[3][3], + + m[2][0]*mat.m[0][0] + m[2][1]*mat.m[1][0] + m[2][2]*mat.m[2][0] + m[2][3]*mat.m[3][0], + m[2][0]*mat.m[0][1] + m[2][1]*mat.m[1][1] + m[2][2]*mat.m[2][1] + m[2][3]*mat.m[3][1], + m[2][0]*mat.m[0][2] + m[2][1]*mat.m[1][2] + m[2][2]*mat.m[2][2] + m[2][3]*mat.m[3][2], + m[2][0]*mat.m[0][3] + m[2][1]*mat.m[1][3] + m[2][2]*mat.m[2][3] + m[2][3]*mat.m[3][3], + + m[3][0]*mat.m[0][0] + m[3][1]*mat.m[1][0] + m[3][2]*mat.m[2][0] + m[3][3]*mat.m[3][0], + m[3][0]*mat.m[0][1] + m[3][1]*mat.m[1][1] + m[3][2]*mat.m[2][1] + m[3][3]*mat.m[3][1], + m[3][0]*mat.m[0][2] + m[3][1]*mat.m[1][2] + m[3][2]*mat.m[2][2] + m[3][3]*mat.m[3][2], + m[3][0]*mat.m[0][3] + m[3][1]*mat.m[1][3] + m[3][2]*mat.m[2][3] + m[3][3]*mat.m[3][3]); + } + + //! Operator for HPoint Mul = Matrix4x4 * HPoint; + inline_ HPoint operator*(const HPoint& v) const { return HPoint(GetRow(0)|v, GetRow(1)|v, GetRow(2)|v, GetRow(3)|v); } + + //! Operator for Point Mul = Matrix4x4 * Point; + inline_ Point operator*(const Point& v) const + { + return Point( m[0][0]*v.x + m[0][1]*v.y + m[0][2]*v.z + m[0][3], + m[1][0]*v.x + m[1][1]*v.y + m[1][2]*v.z + m[1][3], + m[2][0]*v.x + m[2][1]*v.y + m[2][2]*v.z + m[2][3] ); + } + + //! Operator for Matrix4x4 Scale = Matrix4x4 * float; + inline_ Matrix4x4 operator*(float s) const + { + return Matrix4x4( + m[0][0]*s, m[0][1]*s, m[0][2]*s, m[0][3]*s, + m[1][0]*s, m[1][1]*s, m[1][2]*s, m[1][3]*s, + m[2][0]*s, m[2][1]*s, m[2][2]*s, m[2][3]*s, + m[3][0]*s, m[3][1]*s, m[3][2]*s, m[3][3]*s); + } + + //! Operator for Matrix4x4 Scale = float * Matrix4x4; + inline_ friend Matrix4x4 operator*(float s, const Matrix4x4& mat) + { + return Matrix4x4( + s*mat.m[0][0], s*mat.m[0][1], s*mat.m[0][2], s*mat.m[0][3], + s*mat.m[1][0], s*mat.m[1][1], s*mat.m[1][2], s*mat.m[1][3], + s*mat.m[2][0], s*mat.m[2][1], s*mat.m[2][2], s*mat.m[2][3], + s*mat.m[3][0], s*mat.m[3][1], s*mat.m[3][2], s*mat.m[3][3]); + } + + //! Operator for Matrix4x4 Div = Matrix4x4 / float; + inline_ Matrix4x4 operator/(float s) const + { + if(s) s = 1.0f / s; + + return Matrix4x4( + m[0][0]*s, m[0][1]*s, m[0][2]*s, m[0][3]*s, + m[1][0]*s, m[1][1]*s, m[1][2]*s, m[1][3]*s, + m[2][0]*s, m[2][1]*s, m[2][2]*s, m[2][3]*s, + m[3][0]*s, m[3][1]*s, m[3][2]*s, m[3][3]*s); + } + + //! Operator for Matrix4x4 Div = float / Matrix4x4; + inline_ friend Matrix4x4 operator/(float s, const Matrix4x4& mat) + { + return Matrix4x4( + s/mat.m[0][0], s/mat.m[0][1], s/mat.m[0][2], s/mat.m[0][3], + s/mat.m[1][0], s/mat.m[1][1], s/mat.m[1][2], s/mat.m[1][3], + s/mat.m[2][0], s/mat.m[2][1], s/mat.m[2][2], s/mat.m[2][3], + s/mat.m[3][0], s/mat.m[3][1], s/mat.m[3][2], s/mat.m[3][3]); + } + + //! Operator for Matrix4x4 += Matrix4x4; + inline_ Matrix4x4& operator+=(const Matrix4x4& mat) + { + m[0][0]+=mat.m[0][0]; m[0][1]+=mat.m[0][1]; m[0][2]+=mat.m[0][2]; m[0][3]+=mat.m[0][3]; + m[1][0]+=mat.m[1][0]; m[1][1]+=mat.m[1][1]; m[1][2]+=mat.m[1][2]; m[1][3]+=mat.m[1][3]; + m[2][0]+=mat.m[2][0]; m[2][1]+=mat.m[2][1]; m[2][2]+=mat.m[2][2]; m[2][3]+=mat.m[2][3]; + m[3][0]+=mat.m[3][0]; m[3][1]+=mat.m[3][1]; m[3][2]+=mat.m[3][2]; m[3][3]+=mat.m[3][3]; + return *this; + } + + //! Operator for Matrix4x4 -= Matrix4x4; + inline_ Matrix4x4& operator-=(const Matrix4x4& mat) + { + m[0][0]-=mat.m[0][0]; m[0][1]-=mat.m[0][1]; m[0][2]-=mat.m[0][2]; m[0][3]-=mat.m[0][3]; + m[1][0]-=mat.m[1][0]; m[1][1]-=mat.m[1][1]; m[1][2]-=mat.m[1][2]; m[1][3]-=mat.m[1][3]; + m[2][0]-=mat.m[2][0]; m[2][1]-=mat.m[2][1]; m[2][2]-=mat.m[2][2]; m[2][3]-=mat.m[2][3]; + m[3][0]-=mat.m[3][0]; m[3][1]-=mat.m[3][1]; m[3][2]-=mat.m[3][2]; m[3][3]-=mat.m[3][3]; + return *this; + } + + //! Operator for Matrix4x4 *= Matrix4x4; + Matrix4x4& operator*=(const Matrix4x4& mat) + { + HPoint TempRow; + + GetRow(0, TempRow); + m[0][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0] + TempRow.w*mat.m[3][0]; + m[0][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1] + TempRow.w*mat.m[3][1]; + m[0][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2] + TempRow.w*mat.m[3][2]; + m[0][3] = TempRow.x*mat.m[0][3] + TempRow.y*mat.m[1][3] + TempRow.z*mat.m[2][3] + TempRow.w*mat.m[3][3]; + + GetRow(1, TempRow); + m[1][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0] + TempRow.w*mat.m[3][0]; + m[1][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1] + TempRow.w*mat.m[3][1]; + m[1][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2] + TempRow.w*mat.m[3][2]; + m[1][3] = TempRow.x*mat.m[0][3] + TempRow.y*mat.m[1][3] + TempRow.z*mat.m[2][3] + TempRow.w*mat.m[3][3]; + + GetRow(2, TempRow); + m[2][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0] + TempRow.w*mat.m[3][0]; + m[2][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1] + TempRow.w*mat.m[3][1]; + m[2][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2] + TempRow.w*mat.m[3][2]; + m[2][3] = TempRow.x*mat.m[0][3] + TempRow.y*mat.m[1][3] + TempRow.z*mat.m[2][3] + TempRow.w*mat.m[3][3]; + + GetRow(3, TempRow); + m[3][0] = TempRow.x*mat.m[0][0] + TempRow.y*mat.m[1][0] + TempRow.z*mat.m[2][0] + TempRow.w*mat.m[3][0]; + m[3][1] = TempRow.x*mat.m[0][1] + TempRow.y*mat.m[1][1] + TempRow.z*mat.m[2][1] + TempRow.w*mat.m[3][1]; + m[3][2] = TempRow.x*mat.m[0][2] + TempRow.y*mat.m[1][2] + TempRow.z*mat.m[2][2] + TempRow.w*mat.m[3][2]; + m[3][3] = TempRow.x*mat.m[0][3] + TempRow.y*mat.m[1][3] + TempRow.z*mat.m[2][3] + TempRow.w*mat.m[3][3]; + + return *this; + } + + //! Operator for Matrix4x4 *= float; + inline_ Matrix4x4& operator*=(float s) + { + m[0][0]*=s; m[0][1]*=s; m[0][2]*=s; m[0][3]*=s; + m[1][0]*=s; m[1][1]*=s; m[1][2]*=s; m[1][3]*=s; + m[2][0]*=s; m[2][1]*=s; m[2][2]*=s; m[2][3]*=s; + m[3][0]*=s; m[3][1]*=s; m[3][2]*=s; m[3][3]*=s; + return *this; + } + + //! Operator for Matrix4x4 /= float; + inline_ Matrix4x4& operator/=(float s) + { + if(s) s = 1.0f / s; + m[0][0]*=s; m[0][1]*=s; m[0][2]*=s; m[0][3]*=s; + m[1][0]*=s; m[1][1]*=s; m[1][2]*=s; m[1][3]*=s; + m[2][0]*=s; m[2][1]*=s; m[2][2]*=s; m[2][3]*=s; + m[3][0]*=s; m[3][1]*=s; m[3][2]*=s; m[3][3]*=s; + return *this; + } + + inline_ const HPoint& operator[](int row) const { return *(const HPoint*)&m[row][0]; } + inline_ HPoint& operator[](int row) { return *(HPoint*)&m[row][0]; } + + public: + + float m[4][4]; + }; + + //! Quickly rotates & translates a vector, using the 4x3 part of a 4x4 matrix + inline_ void TransformPoint4x3(Point& dest, const Point& source, const Matrix4x4& rot) + { + dest.x = rot.m[3][0] + source.x * rot.m[0][0] + source.y * rot.m[1][0] + source.z * rot.m[2][0]; + dest.y = rot.m[3][1] + source.x * rot.m[0][1] + source.y * rot.m[1][1] + source.z * rot.m[2][1]; + dest.z = rot.m[3][2] + source.x * rot.m[0][2] + source.y * rot.m[1][2] + source.z * rot.m[2][2]; + } + + //! Quickly rotates a vector, using the 3x3 part of a 4x4 matrix + inline_ void TransformPoint3x3(Point& dest, const Point& source, const Matrix4x4& rot) + { + dest.x = source.x * rot.m[0][0] + source.y * rot.m[1][0] + source.z * rot.m[2][0]; + dest.y = source.x * rot.m[0][1] + source.y * rot.m[1][1] + source.z * rot.m[2][1]; + dest.z = source.x * rot.m[0][2] + source.y * rot.m[1][2] + source.z * rot.m[2][2]; + } + + ICEMATHS_API void InvertPRMatrix(Matrix4x4& dest, const Matrix4x4& src); + +#endif // __ICEMATRIX4X4_H__ + diff --git a/Opcode/Ice/IceMemoryMacros.h b/Opcode/Ice/IceMemoryMacros.h new file mode 100644 index 0000000..490ecd1 --- /dev/null +++ b/Opcode/Ice/IceMemoryMacros.h @@ -0,0 +1,105 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains all memory macros. + * \file IceMemoryMacros.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEMEMORYMACROS_H__ +#define __ICEMEMORYMACROS_H__ + +#undef ZeroMemory +#undef CopyMemory +#undef MoveMemory +#undef FillMemory + + //! Clears a buffer. + //! \param addr [in] buffer address + //! \param size [in] buffer length + //! \see FillMemory + //! \see StoreDwords + //! \see CopyMemory + //! \see MoveMemory + inline_ void ZeroMemory(void* addr, udword size) { memset(addr, 0, size); } + + //! Fills a buffer with a given byte. + //! \param addr [in] buffer address + //! \param size [in] buffer length + //! \param val [in] the byte value + //! \see StoreDwords + //! \see ZeroMemory + //! \see CopyMemory + //! \see MoveMemory + inline_ void FillMemory(void* dest, udword size, ubyte val) { memset(dest, val, size); } + + //! Fills a buffer with a given dword. + //! \param addr [in] buffer address + //! \param nb [in] number of dwords to write + //! \param value [in] the dword value + //! \see FillMemory + //! \see ZeroMemory + //! \see CopyMemory + //! \see MoveMemory + //! \warning writes nb*4 bytes ! + inline_ void StoreDwords(udword* dest, udword nb, udword value) + { + // The asm code below **SHOULD** be equivalent to one of those C versions + // or the other if your compiled is good: (checked on VC++ 6.0) + // + // 1) while(nb--) *dest++ = value; + // + // 2) for(udword i=0;iRelease(); (x) = null; } //!< Safe D3D-style release + #define SAFE_DESTRUCT(x) if (x) { (x)->SelfDestruct(); (x) = null; } //!< Safe ICE-style release + +#ifdef __ICEERROR_H__ + #define CHECKALLOC(x) if(!x) return SetIceError("Out of memory.", EC_OUT_OF_MEMORY); //!< Standard alloc checking. HANDLE WITH CARE. +#else + #define CHECKALLOC(x) if(!x) return false; +#endif + + //! Standard allocation cycle + #define SAFE_ALLOC(ptr, type, count) DELETEARRAY(ptr); ptr = new type[count]; CHECKALLOC(ptr); + +#endif // __ICEMEMORYMACROS_H__ diff --git a/Opcode/Ice/IceOBB.cpp b/Opcode/Ice/IceOBB.cpp new file mode 100644 index 0000000..439c58c --- /dev/null +++ b/Opcode/Ice/IceOBB.cpp @@ -0,0 +1,323 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains OBB-related code. + * \file IceOBB.cpp + * \author Pierre Terdiman + * \date January, 29, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * An Oriented Bounding Box (OBB). + * \class OBB + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Tests if a point is contained within the OBB. + * \param p [in] the world point to test + * \return true if inside the OBB + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool OBB::ContainsPoint(const IcePoint& p) const +{ + // IcePoint in OBB test using lazy evaluation and early exits + + // Translate to box space + IcePoint RelPoint = p - mCenter; + + // IcePoint * mRot maps from box space to world space + // mRot * IcePoint maps from world space to box space (what we need here) + + float f = mRot.m[0][0] * RelPoint.x + mRot.m[0][1] * RelPoint.y + mRot.m[0][2] * RelPoint.z; + if(f >= mExtents.x || f <= -mExtents.x) return false; + + f = mRot.m[1][0] * RelPoint.x + mRot.m[1][1] * RelPoint.y + mRot.m[1][2] * RelPoint.z; + if(f >= mExtents.y || f <= -mExtents.y) return false; + + f = mRot.m[2][0] * RelPoint.x + mRot.m[2][1] * RelPoint.y + mRot.m[2][2] * RelPoint.z; + if(f >= mExtents.z || f <= -mExtents.z) return false; + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds an OBB from an AABB and a world transform. + * \param aabb [in] the aabb + * \param mat [in] the world transform + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void OBB::Create(const AABB& aabb, const Matrix4x4& mat) +{ + // Note: must be coherent with Rotate() + + aabb.GetCenter(mCenter); + aabb.GetExtents(mExtents); + // Here we have the same as OBB::Rotate(mat) where the obb is (mCenter, mExtents, Identity). + + // So following what's done in Rotate: + // - x-form the center + mCenter *= mat; + // - combine rotation with identity, i.e. just use given matrix + mRot = mat; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the obb planes. + * \param planes [out] 6 box planes + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool OBB::ComputePlanes(Plane* planes) const +{ + // Checkings + if(!planes) return false; + + IcePoint Axis0 = mRot[0]; + IcePoint Axis1 = mRot[1]; + IcePoint Axis2 = mRot[2]; + + // Writes normals + planes[0].n = Axis0; + planes[1].n = -Axis0; + planes[2].n = Axis1; + planes[3].n = -Axis1; + planes[4].n = Axis2; + planes[5].n = -Axis2; + + // Compute a point on each plane + IcePoint p0 = mCenter + Axis0 * mExtents.x; + IcePoint p1 = mCenter - Axis0 * mExtents.x; + IcePoint p2 = mCenter + Axis1 * mExtents.y; + IcePoint p3 = mCenter - Axis1 * mExtents.y; + IcePoint p4 = mCenter + Axis2 * mExtents.z; + IcePoint p5 = mCenter - Axis2 * mExtents.z; + + // Compute d + planes[0].d = -(planes[0].n|p0); + planes[1].d = -(planes[1].n|p1); + planes[2].d = -(planes[2].n|p2); + planes[3].d = -(planes[3].n|p3); + planes[4].d = -(planes[4].n|p4); + planes[5].d = -(planes[5].n|p5); + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the obb points. + * \param pts [out] 8 box points + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool OBB::ComputePoints(IcePoint* pts) const +{ + // Checkings + if(!pts) return false; + + IcePoint Axis0 = mRot[0]; + IcePoint Axis1 = mRot[1]; + IcePoint Axis2 = mRot[2]; + + Axis0 *= mExtents.x; + Axis1 *= mExtents.y; + Axis2 *= mExtents.z; + + // 7+------+6 0 = --- + // /| /| 1 = +-- + // / | / | 2 = ++- + // / 4+---/--+5 3 = -+- + // 3+------+2 / y z 4 = --+ + // | / | / | / 5 = +-+ + // |/ |/ |/ 6 = +++ + // 0+------+1 *---x 7 = -++ + + pts[0] = mCenter - Axis0 - Axis1 - Axis2; + pts[1] = mCenter + Axis0 - Axis1 - Axis2; + pts[2] = mCenter + Axis0 + Axis1 - Axis2; + pts[3] = mCenter - Axis0 + Axis1 - Axis2; + pts[4] = mCenter - Axis0 - Axis1 + Axis2; + pts[5] = mCenter + Axis0 - Axis1 + Axis2; + pts[6] = mCenter + Axis0 + Axis1 + Axis2; + pts[7] = mCenter - Axis0 + Axis1 + Axis2; + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes vertex normals. + * \param pts [out] 8 box points + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool OBB::ComputeVertexNormals(IcePoint* pts) const +{ + static float VertexNormals[] = + { + -INVSQRT3, -INVSQRT3, -INVSQRT3, + INVSQRT3, -INVSQRT3, -INVSQRT3, + INVSQRT3, INVSQRT3, -INVSQRT3, + -INVSQRT3, INVSQRT3, -INVSQRT3, + -INVSQRT3, -INVSQRT3, INVSQRT3, + INVSQRT3, -INVSQRT3, INVSQRT3, + INVSQRT3, INVSQRT3, INVSQRT3, + -INVSQRT3, INVSQRT3, INVSQRT3 + }; + + if(!pts) return false; + + const IcePoint* VN = (const IcePoint*)VertexNormals; + for(udword i=0;i<8;i++) + { + pts[i] = VN[i] * mRot; + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Returns edges. + * \return 24 indices (12 edges) indexing the list returned by ComputePoints() + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +const udword* OBB::GetEdges() const +{ + static udword Indices[] = { + 0, 1, 1, 2, 2, 3, 3, 0, + 7, 6, 6, 5, 5, 4, 4, 7, + 1, 5, 6, 2, + 3, 7, 4, 0 + }; + return Indices; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Returns local edge normals. + * \return edge normals in local space + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +const IcePoint* OBB::GetLocalEdgeNormals() const +{ + static float EdgeNormals[] = + { + 0, -INVSQRT2, -INVSQRT2, // 0-1 + INVSQRT2, 0, -INVSQRT2, // 1-2 + 0, INVSQRT2, -INVSQRT2, // 2-3 + -INVSQRT2, 0, -INVSQRT2, // 3-0 + + 0, INVSQRT2, INVSQRT2, // 7-6 + INVSQRT2, 0, INVSQRT2, // 6-5 + 0, -INVSQRT2, INVSQRT2, // 5-4 + -INVSQRT2, 0, INVSQRT2, // 4-7 + + INVSQRT2, -INVSQRT2, 0, // 1-5 + INVSQRT2, INVSQRT2, 0, // 6-2 + -INVSQRT2, INVSQRT2, 0, // 3-7 + -INVSQRT2, -INVSQRT2, 0 // 4-0 + }; + return (const IcePoint*)EdgeNormals; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Returns world edge normal + * \param edge_index [in] 0 <= edge index < 12 + * \param world_normal [out] edge normal in world space + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void OBB::ComputeWorldEdgeNormal(udword edge_index, IcePoint& world_normal) const +{ + ASSERT(edge_index<12); + world_normal = GetLocalEdgeNormals()[edge_index] * mRot; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes an LSS surrounding the OBB. + * \param lss [out] the LSS + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void OBB::ComputeLSS(LSS& lss) const +{ + IcePoint Axis0 = mRot[0]; + IcePoint Axis1 = mRot[1]; + IcePoint Axis2 = mRot[2]; + + switch(mExtents.LargestAxis()) + { + case 0: + lss.mRadius = (mExtents.y + mExtents.z)*0.5f; + lss.mP0 = mCenter + Axis0 * (mExtents.x - lss.mRadius); + lss.mP1 = mCenter - Axis0 * (mExtents.x - lss.mRadius); + break; + case 1: + lss.mRadius = (mExtents.x + mExtents.z)*0.5f; + lss.mP0 = mCenter + Axis1 * (mExtents.y - lss.mRadius); + lss.mP1 = mCenter - Axis1 * (mExtents.y - lss.mRadius); + break; + case 2: + lss.mRadius = (mExtents.x + mExtents.y)*0.5f; + lss.mP0 = mCenter + Axis2 * (mExtents.z - lss.mRadius); + lss.mP1 = mCenter - Axis2 * (mExtents.z - lss.mRadius); + break; + } +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks the OBB is inside another OBB. + * \param box [in] the other OBB + * \return TRUE if we're inside the other box + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +BOOL OBB::IsInside(const OBB& box) const +{ + // Make a 4x4 from the box & inverse it + Matrix4x4 M0Inv; + { + Matrix4x4 M0 = box.mRot; + M0.SetTrans(box.mCenter); + InvertPRMatrix(M0Inv, M0); + } + + // With our inversed 4x4, create box1 in space of box0 + OBB _1in0; + Rotate(M0Inv, _1in0); + + // This should cancel out box0's rotation, i.e. it's now an AABB. + // => Center(0,0,0), Rot(identity) + + // The two boxes are in the same space so now we can compare them. + + // Create the AABB of (box1 in space of box0) + const Matrix3x3& mtx = _1in0.mRot; + + float f = fabsf(mtx.m[0][0] * mExtents.x) + fabsf(mtx.m[1][0] * mExtents.y) + fabsf(mtx.m[2][0] * mExtents.z) - box.mExtents.x; + if(f > _1in0.mCenter.x) return FALSE; + if(-f < _1in0.mCenter.x) return FALSE; + + f = fabsf(mtx.m[0][1] * mExtents.x) + fabsf(mtx.m[1][1] * mExtents.y) + fabsf(mtx.m[2][1] * mExtents.z) - box.mExtents.y; + if(f > _1in0.mCenter.y) return FALSE; + if(-f < _1in0.mCenter.y) return FALSE; + + f = fabsf(mtx.m[0][2] * mExtents.x) + fabsf(mtx.m[1][2] * mExtents.y) + fabsf(mtx.m[2][2] * mExtents.z) - box.mExtents.z; + if(f > _1in0.mCenter.z) return FALSE; + if(-f < _1in0.mCenter.z) return FALSE; + + return TRUE; +} diff --git a/Opcode/Ice/IceOBB.h b/Opcode/Ice/IceOBB.h new file mode 100644 index 0000000..4747f7f --- /dev/null +++ b/Opcode/Ice/IceOBB.h @@ -0,0 +1,177 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains OBB-related code. (oriented bounding box) + * \file IceOBB.h + * \author Pierre Terdiman + * \date January, 13, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEOBB_H__ +#define __ICEOBB_H__ + + // Forward declarations + class LSS; + + class ICEMATHS_API OBB + { + public: + //! Constructor + inline_ OBB() {} + //! Constructor + inline_ OBB(const Point& center, const Point& extents, const Matrix3x3& rot) : mCenter(center), mExtents(extents), mRot(rot) {} + //! Destructor + inline_ ~OBB() {} + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Setups an empty OBB. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void SetEmpty() + { + mCenter.Zero(); + mExtents.Set(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); + mRot.Identity(); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Tests if a point is contained within the OBB. + * \param p [in] the world point to test + * \return true if inside the OBB + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool ContainsPoint(const Point& p) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Builds an OBB from an AABB and a world transform. + * \param aabb [in] the aabb + * \param mat [in] the world transform + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void Create(const AABB& aabb, const Matrix4x4& mat); + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Recomputes the OBB after an arbitrary transform by a 4x4 matrix. + * \param mtx [in] the transform matrix + * \param obb [out] the transformed OBB + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void Rotate(const Matrix4x4& mtx, OBB& obb) const + { + // The extents remain constant + obb.mExtents = mExtents; + // The center gets x-formed + obb.mCenter = mCenter * mtx; + // Combine rotations + obb.mRot = mRot * Matrix3x3(mtx); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Checks the OBB is valid. + * \return true if the box is valid + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ BOOL IsValid() const + { + // Consistency condition for (Center, Extents) boxes: Extents >= 0.0f + if(mExtents.x < 0.0f) return FALSE; + if(mExtents.y < 0.0f) return FALSE; + if(mExtents.z < 0.0f) return FALSE; + return TRUE; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the obb planes. + * \param planes [out] 6 box planes + * \return true if success + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool ComputePlanes(Plane* planes) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes the obb points. + * \param pts [out] 8 box points + * \return true if success + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool ComputePoints(Point* pts) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes vertex normals. + * \param pts [out] 8 box points + * \return true if success + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + bool ComputeVertexNormals(Point* pts) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Returns edges. + * \return 24 indices (12 edges) indexing the list returned by ComputePoints() + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + const udword* GetEdges() const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Returns local edge normals. + * \return edge normals in local space + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + const Point* GetLocalEdgeNormals() const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Returns world edge normal + * \param edge_index [in] 0 <= edge index < 12 + * \param world_normal [out] edge normal in world space + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void ComputeWorldEdgeNormal(udword edge_index, Point& world_normal) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes an LSS surrounding the OBB. + * \param lss [out] the LSS + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + void ComputeLSS(LSS& lss) const; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Checks the OBB is inside another OBB. + * \param box [in] the other OBB + * \return TRUE if we're inside the other box + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + BOOL IsInside(const OBB& box) const; + + inline_ const Point& GetCenter() const { return mCenter; } + inline_ const Point& GetExtents() const { return mExtents; } + inline_ const Matrix3x3& GetRot() const { return mRot; } + + inline_ void GetRotatedExtents(Matrix3x3& extents) const + { + extents = mRot; + extents.Scale(mExtents); + } + + Point mCenter; //!< B for Box + Point mExtents; //!< B for Bounding + Matrix3x3 mRot; //!< O for Oriented + + // Orientation is stored in row-major format, + // i.e. rows = eigen vectors of the covariance matrix + }; + +#endif // __ICEOBB_H__ diff --git a/Opcode/Ice/IcePairs.h b/Opcode/Ice/IcePairs.h new file mode 100644 index 0000000..35e3a07 --- /dev/null +++ b/Opcode/Ice/IcePairs.h @@ -0,0 +1,45 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a simple pair class. + * \file IcePairs.h + * \author Pierre Terdiman + * \date January, 13, 2003 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEPAIRS_H__ +#define __ICEPAIRS_H__ + + //! A generic couple structure + struct ICECORE_API Pair + { + inline_ Pair() {} + inline_ Pair(udword i0, udword i1) : id0(i0), id1(i1) {} + + udword id0; //!< First index of the pair + udword id1; //!< Second index of the pair + }; + + class ICECORE_API Pairs : private Container + { + public: + // Constructor / Destructor + Pairs() {} + ~Pairs() {} + + inline_ udword GetNbPairs() const { return GetNbEntries()>>1; } + inline_ const Pair* GetPairs() const { return (const Pair*)GetEntries(); } + inline_ const Pair* GetPair(udword i) const { return (const Pair*)&GetEntries()[i+i]; } + + inline_ BOOL HasPairs() const { return IsNotEmpty(); } + + inline_ void ResetPairs() { Reset(); } + inline_ void DeleteLastPair() { DeleteLastEntry(); DeleteLastEntry(); } + + inline_ void AddPair(const Pair& p) { Add(p.id0).Add(p.id1); } + inline_ void AddPair(udword id0, udword id1) { Add(id0).Add(id1); } + }; + +#endif // __ICEPAIRS_H__ diff --git a/Opcode/Ice/IcePlane.cpp b/Opcode/Ice/IcePlane.cpp new file mode 100644 index 0000000..36fe473 --- /dev/null +++ b/Opcode/Ice/IcePlane.cpp @@ -0,0 +1,45 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for planes. + * \file IcePlane.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Plane class. + * \class Plane + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the plane equation from 3 points. + * \param p0 [in] first point + * \param p1 [in] second point + * \param p2 [in] third point + * \return Self-reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Plane& Plane::Set(const Point& p0, const Point& p1, const Point& p2) +{ + Point Edge0 = p1 - p0; + Point Edge1 = p2 - p0; + + n = Edge0 ^ Edge1; + n.Normalize(); + + d = -(p0 | n); + + return *this; +} diff --git a/Opcode/Ice/IcePlane.h b/Opcode/Ice/IcePlane.h new file mode 100644 index 0000000..0e0604c --- /dev/null +++ b/Opcode/Ice/IcePlane.h @@ -0,0 +1,113 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for planes. + * \file IcePlane.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEPLANE_H__ +#define __ICEPLANE_H__ + + #define PLANE_EPSILON (1.0e-7f) + + class ICEMATHS_API Plane + { + public: + //! Constructor + inline_ Plane() { } + //! Constructor from a normal and a distance + inline_ Plane(float nx, float ny, float nz, float d) { Set(nx, ny, nz, d); } + //! Constructor from a point on the plane and a normal + inline_ Plane(const Point& p, const Point& n) { Set(p, n); } + //! Constructor from three points + inline_ Plane(const Point& p0, const Point& p1, const Point& p2) { Set(p0, p1, p2); } + //! Constructor from a normal and a distance + inline_ Plane(const Point& _n, float _d) { n = _n; d = _d; } + //! Copy constructor + inline_ Plane(const Plane& plane) : n(plane.n), d(plane.d) { } + //! Destructor + inline_ ~Plane() { } + + inline_ Plane& Zero() { n.Zero(); d = 0.0f; return *this; } + inline_ Plane& Set(float nx, float ny, float nz, float _d) { n.Set(nx, ny, nz); d = _d; return *this; } + inline_ Plane& Set(const Point& p, const Point& _n) { n = _n; d = - p | _n; return *this; } + Plane& Set(const Point& p0, const Point& p1, const Point& p2); + + inline_ float Distance(const Point& p) const { return (p | n) + d; } + inline_ bool Belongs(const Point& p) const { return fabsf(Distance(p)) < PLANE_EPSILON; } + + inline_ void Normalize() + { + float Denom = 1.0f / n.Magnitude(); + n.x *= Denom; + n.y *= Denom; + n.z *= Denom; + d *= Denom; + } + public: + // Members + Point n; //!< The normal to the plane + float d; //!< The distance from the origin + + // Cast operators + inline_ operator Point() const { return n; } + inline_ operator HPoint() const { return HPoint(n, d); } + + // Arithmetic operators + inline_ Plane operator*(const Matrix4x4& m) const + { + // Old code from Irion. Kept for reference. + Plane Ret(*this); + return Ret *= m; + } + + inline_ Plane& operator*=(const Matrix4x4& m) + { + // Old code from Irion. Kept for reference. + Point n2 = HPoint(n, 0.0f) * m; + d = -((Point) (HPoint( -d*n, 1.0f ) * m) | n2); + n = n2; + return *this; + } + }; + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Transforms a plane by a 4x4 matrix. Same as Plane * Matrix4x4 operator, but faster. + * \param transformed [out] transformed plane + * \param plane [in] source plane + * \param transform [in] transform matrix + * \warning the plane normal must be unit-length + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void TransformPlane(Plane& transformed, const Plane& plane, const Matrix4x4& transform) + { + // Rotate the normal using the rotation part of the 4x4 matrix + transformed.n = plane.n * Matrix3x3(transform); + + // Compute new d + transformed.d = plane.d - (Point(transform.GetTrans())|transformed.n); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Transforms a plane by a 4x4 matrix. Same as Plane * Matrix4x4 operator, but faster. + * \param plane [in/out] source plane (transformed on return) + * \param transform [in] transform matrix + * \warning the plane normal must be unit-length + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void TransformPlane(Plane& plane, const Matrix4x4& transform) + { + // Rotate the normal using the rotation part of the 4x4 matrix + plane.n *= Matrix3x3(transform); + + // Compute new d + plane.d -= Point(transform.GetTrans())|plane.n; + } + +#endif // __ICEPLANE_H__ diff --git a/Opcode/Ice/IcePoint.cpp b/Opcode/Ice/IcePoint.cpp new file mode 100644 index 0000000..9fd7570 --- /dev/null +++ b/Opcode/Ice/IcePoint.cpp @@ -0,0 +1,193 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 3D vectors. + * \file IcePoint.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * 3D point. + * + * The name is "Point" instead of "Vector" since a vector is N-dimensional, whereas a point is an implicit "vector of dimension 3". + * So the choice was between "Point" and "Vector3", the first one looked better (IMHO). + * + * Some people, then, use a typedef to handle both points & vectors using the same class: typedef Point Vector3; + * This is bad since it opens the door to a lot of confusion while reading the code. I know it may sounds weird but check this out: + * + * \code + * Point P0,P1 = some 3D points; + * Point Delta = P1 - P0; + * \endcode + * + * This compiles fine, although you should have written: + * + * \code + * Point P0,P1 = some 3D points; + * Vector3 Delta = P1 - P0; + * \endcode + * + * Subtle things like this are not caught at compile-time, and when you find one in the code, you never know whether it's a mistake + * from the author or something you don't get. + * + * One way to handle it at compile-time would be to use different classes for Point & Vector3, only overloading operator "-" for vectors. + * But then, you get a lot of redundant code in thoses classes, and basically it's really a lot of useless work. + * + * Another way would be to use homogeneous points: w=1 for points, w=0 for vectors. That's why the HPoint class exists. Now, to store + * your model's vertices and in most cases, you really want to use Points to save ram. + * + * \class Point + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Creates a positive unit random vector. + * \return Self-reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Point& Point::PositiveUnitRandomVector() +{ + x = UnitRandomFloat(); + y = UnitRandomFloat(); + z = UnitRandomFloat(); + Normalize(); + return *this; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Creates a unit random vector. + * \return Self-reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +Point& Point::UnitRandomVector() +{ + x = UnitRandomFloat() - 0.5f; + y = UnitRandomFloat() - 0.5f; + z = UnitRandomFloat() - 0.5f; + Normalize(); + return *this; +} + +// Cast operator +// WARNING: not inlined +Point::operator HPoint() const { return HPoint(x, y, z, 0.0f); } + +Point& Point::Refract(const Point& eye, const Point& n, float refractindex, Point& refracted) +{ + // Point EyePt = eye position + // Point p = current vertex + // Point n = vertex normal + // Point rv = refracted vector + // Eye vector - doesn't need to be normalized + Point Env; + Env.x = eye.x - x; + Env.y = eye.y - y; + Env.z = eye.z - z; + + float NDotE = n|Env; + float NDotN = n|n; + NDotE /= refractindex; + + // Refracted vector + refracted = n*NDotE - Env*NDotN; + + return *this; +} + +Point& Point::ProjectToPlane(const Plane& p) +{ + *this-= (p.d + (*this|p.n))*p.n; + return *this; +} + +void Point::ProjectToScreen(float halfrenderwidth, float halfrenderheight, const Matrix4x4& mat, HPoint& projected) const +{ + projected = HPoint(x, y, z, 1.0f) * mat; + projected.w = 1.0f / projected.w; + + projected.x*=projected.w; + projected.y*=projected.w; + projected.z*=projected.w; + + projected.x *= halfrenderwidth; projected.x += halfrenderwidth; + projected.y *= -halfrenderheight; projected.y += halfrenderheight; +} + +void Point::SetNotUsed() +{ + // We use a particular integer pattern : 0xffffffff everywhere. This is a NAN. + IR(x) = 0xffffffff; + IR(y) = 0xffffffff; + IR(z) = 0xffffffff; +} + +BOOL Point::IsNotUsed() const +{ + if(IR(x)!=0xffffffff) return FALSE; + if(IR(y)!=0xffffffff) return FALSE; + if(IR(z)!=0xffffffff) return FALSE; + return TRUE; +} + +Point& Point::Mult(const Matrix3x3& mat, const Point& a) +{ + x = a.x * mat.m[0][0] + a.y * mat.m[0][1] + a.z * mat.m[0][2]; + y = a.x * mat.m[1][0] + a.y * mat.m[1][1] + a.z * mat.m[1][2]; + z = a.x * mat.m[2][0] + a.y * mat.m[2][1] + a.z * mat.m[2][2]; + return *this; +} + +Point& Point::Mult2(const Matrix3x3& mat1, const Point& a1, const Matrix3x3& mat2, const Point& a2) +{ + x = a1.x * mat1.m[0][0] + a1.y * mat1.m[0][1] + a1.z * mat1.m[0][2] + a2.x * mat2.m[0][0] + a2.y * mat2.m[0][1] + a2.z * mat2.m[0][2]; + y = a1.x * mat1.m[1][0] + a1.y * mat1.m[1][1] + a1.z * mat1.m[1][2] + a2.x * mat2.m[1][0] + a2.y * mat2.m[1][1] + a2.z * mat2.m[1][2]; + z = a1.x * mat1.m[2][0] + a1.y * mat1.m[2][1] + a1.z * mat1.m[2][2] + a2.x * mat2.m[2][0] + a2.y * mat2.m[2][1] + a2.z * mat2.m[2][2]; + return *this; +} + +Point& Point::Mac(const Matrix3x3& mat, const Point& a) +{ + x += a.x * mat.m[0][0] + a.y * mat.m[0][1] + a.z * mat.m[0][2]; + y += a.x * mat.m[1][0] + a.y * mat.m[1][1] + a.z * mat.m[1][2]; + z += a.x * mat.m[2][0] + a.y * mat.m[2][1] + a.z * mat.m[2][2]; + return *this; +} + +Point& Point::TransMult(const Matrix3x3& mat, const Point& a) +{ + x = a.x * mat.m[0][0] + a.y * mat.m[1][0] + a.z * mat.m[2][0]; + y = a.x * mat.m[0][1] + a.y * mat.m[1][1] + a.z * mat.m[2][1]; + z = a.x * mat.m[0][2] + a.y * mat.m[1][2] + a.z * mat.m[2][2]; + return *this; +} + +Point& Point::Transform(const Point& r, const Matrix3x3& rotpos, const Point& linpos) +{ + x = r.x * rotpos.m[0][0] + r.y * rotpos.m[0][1] + r.z * rotpos.m[0][2] + linpos.x; + y = r.x * rotpos.m[1][0] + r.y * rotpos.m[1][1] + r.z * rotpos.m[1][2] + linpos.y; + z = r.x * rotpos.m[2][0] + r.y * rotpos.m[2][1] + r.z * rotpos.m[2][2] + linpos.z; + return *this; +} + +Point& Point::InvTransform(const Point& r, const Matrix3x3& rotpos, const Point& linpos) +{ + float sx = r.x - linpos.x; + float sy = r.y - linpos.y; + float sz = r.z - linpos.z; + x = sx * rotpos.m[0][0] + sy * rotpos.m[1][0] + sz * rotpos.m[2][0]; + y = sx * rotpos.m[0][1] + sy * rotpos.m[1][1] + sz * rotpos.m[2][1]; + z = sx * rotpos.m[0][2] + sy * rotpos.m[1][2] + sz * rotpos.m[2][2]; + return *this; +} diff --git a/Opcode/Ice/IcePoint.h b/Opcode/Ice/IcePoint.h new file mode 100644 index 0000000..78148d6 --- /dev/null +++ b/Opcode/Ice/IcePoint.h @@ -0,0 +1,528 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for 3D vectors. + * \file IcePoint.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEPOINT_H__ +#define __ICEPOINT_H__ + + // Forward declarations + class HPoint; + class Plane; + class Matrix3x3; + class Matrix4x4; + + #define CROSS2D(a, b) (a.x*b.y - b.x*a.y) + + const float EPSILON2 = 1.0e-20f; + + class ICEMATHS_API Point + { + public: + + //! Empty constructor + inline_ Point() {} + //! Constructor from a single float +// inline_ Point(float val) : x(val), y(val), z(val) {} +// Removed since it introduced the nasty "Point T = *Matrix4x4.GetTrans();" bug....... + //! Constructor from floats + inline_ Point(float _x, float _y, float _z) : x(_x), y(_y), z(_z) {} + //! Constructor from array + inline_ Point(const float f[3]) : x(f[_X]), y(f[_Y]), z(f[_Z]) {} + //! Copy constructor + inline_ Point(const Point& p) : x(p.x), y(p.y), z(p.z) {} + //! Destructor + inline_ ~Point() {} + + //! Clears the vector + inline_ Point& Zero() { x = y = z = 0.0f; return *this; } + + //! + infinity + inline_ Point& SetPlusInfinity() { x = y = z = MAX_FLOAT; return *this; } + //! - infinity + inline_ Point& SetMinusInfinity() { x = y = z = MIN_FLOAT; return *this; } + + //! Sets positive unit random vector + Point& PositiveUnitRandomVector(); + //! Sets unit random vector + Point& UnitRandomVector(); + + //! Assignment from values + inline_ Point& Set(float _x, float _y, float _z) { x = _x; y = _y; z = _z; return *this; } + //! Assignment from array + inline_ Point& Set(const float f[3]) { x = f[_X]; y = f[_Y]; z = f[_Z]; return *this; } + //! Assignment from another point + inline_ Point& Set(const Point& src) { x = src.x; y = src.y; z = src.z; return *this; } + + //! Adds a vector + inline_ Point& Add(const Point& p) { x += p.x; y += p.y; z += p.z; return *this; } + //! Adds a vector + inline_ Point& Add(float _x, float _y, float _z) { x += _x; y += _y; z += _z; return *this; } + //! Adds a vector + inline_ Point& Add(const float f[3]) { x += f[_X]; y += f[_Y]; z += f[_Z]; return *this; } + //! Adds vectors + 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; } + + //! Subtracts a vector + inline_ Point& Sub(const Point& p) { x -= p.x; y -= p.y; z -= p.z; return *this; } + //! Subtracts a vector + inline_ Point& Sub(float _x, float _y, float _z) { x -= _x; y -= _y; z -= _z; return *this; } + //! Subtracts a vector + inline_ Point& Sub(const float f[3]) { x -= f[_X]; y -= f[_Y]; z -= f[_Z]; return *this; } + //! Subtracts vectors + 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; } + + //! this = -this + inline_ Point& Neg() { x = -x; y = -y; z = -z; return *this; } + //! this = -a + inline_ Point& Neg(const Point& a) { x = -a.x; y = -a.y; z = -a.z; return *this; } + + //! Multiplies by a scalar + inline_ Point& Mult(float s) { x *= s; y *= s; z *= s; return *this; } + + //! this = a * scalar + inline_ Point& Mult(const Point& a, float scalar) + { + x = a.x * scalar; + y = a.y * scalar; + z = a.z * scalar; + return *this; + } + + //! this = a + b * scalar + inline_ Point& Mac(const Point& a, const Point& b, float scalar) + { + x = a.x + b.x * scalar; + y = a.y + b.y * scalar; + z = a.z + b.z * scalar; + return *this; + } + + //! this = this + a * scalar + inline_ Point& Mac(const Point& a, float scalar) + { + x += a.x * scalar; + y += a.y * scalar; + z += a.z * scalar; + return *this; + } + + //! this = a - b * scalar + inline_ Point& Msc(const Point& a, const Point& b, float scalar) + { + x = a.x - b.x * scalar; + y = a.y - b.y * scalar; + z = a.z - b.z * scalar; + return *this; + } + + //! this = this - a * scalar + inline_ Point& Msc(const Point& a, float scalar) + { + x -= a.x * scalar; + y -= a.y * scalar; + z -= a.z * scalar; + return *this; + } + + //! this = a + b * scalarb + c * scalarc + inline_ Point& Mac2(const Point& a, const Point& b, float scalarb, const Point& c, float scalarc) + { + x = a.x + b.x * scalarb + c.x * scalarc; + y = a.y + b.y * scalarb + c.y * scalarc; + z = a.z + b.z * scalarb + c.z * scalarc; + return *this; + } + + //! this = a - b * scalarb - c * scalarc + inline_ Point& Msc2(const Point& a, const Point& b, float scalarb, const Point& c, float scalarc) + { + x = a.x - b.x * scalarb - c.x * scalarc; + y = a.y - b.y * scalarb - c.y * scalarc; + z = a.z - b.z * scalarb - c.z * scalarc; + return *this; + } + + //! this = mat * a + inline_ Point& Mult(const Matrix3x3& mat, const Point& a); + + //! this = mat1 * a1 + mat2 * a2 + inline_ Point& Mult2(const Matrix3x3& mat1, const Point& a1, const Matrix3x3& mat2, const Point& a2); + + //! this = this + mat * a + inline_ Point& Mac(const Matrix3x3& mat, const Point& a); + + //! this = transpose(mat) * a + inline_ Point& TransMult(const Matrix3x3& mat, const Point& a); + + //! Linear interpolate between two vectors: this = a + t * (b - a) + inline_ Point& Lerp(const Point& a, const Point& b, float t) + { + x = a.x + t * (b.x - a.x); + y = a.y + t * (b.y - a.y); + z = a.z + t * (b.z - a.z); + return *this; + } + + //! Hermite interpolate between p1 and p2. p0 and p3 are used for finding gradient at p1 and p2. + //! this = p0 * (2t^2 - t^3 - t)/2 + //! + p1 * (3t^3 - 5t^2 + 2)/2 + //! + p2 * (4t^2 - 3t^3 + t)/2 + //! + p3 * (t^3 - t^2)/2 + inline_ Point& Herp(const Point& p0, const Point& p1, const Point& p2, const Point& p3, float t) + { + float t2 = t * t; + float t3 = t2 * t; + float kp0 = (2.0f * t2 - t3 - t) * 0.5f; + float kp1 = (3.0f * t3 - 5.0f * t2 + 2.0f) * 0.5f; + float kp2 = (4.0f * t2 - 3.0f * t3 + t) * 0.5f; + float kp3 = (t3 - t2) * 0.5f; + x = p0.x * kp0 + p1.x * kp1 + p2.x * kp2 + p3.x * kp3; + y = p0.y * kp0 + p1.y * kp1 + p2.y * kp2 + p3.y * kp3; + z = p0.z * kp0 + p1.z * kp1 + p2.z * kp2 + p3.z * kp3; + return *this; + } + + //! this = rotpos * r + linpos + inline_ Point& Transform(const Point& r, const Matrix3x3& rotpos, const Point& linpos); + + //! this = trans(rotpos) * (r - linpos) + inline_ Point& InvTransform(const Point& r, const Matrix3x3& rotpos, const Point& linpos); + + //! Returns MIN(x, y, z); + inline_ float Min() const { return MIN(x, MIN(y, z)); } + //! Returns MAX(x, y, z); + inline_ float Max() const { return MAX(x, MAX(y, z)); } + //! Sets each element to be componentwise minimum + inline_ Point& Min(const Point& p) { x = MIN(x, p.x); y = MIN(y, p.y); z = MIN(z, p.z); return *this; } + //! Sets each element to be componentwise maximum + inline_ Point& Max(const Point& p) { x = MAX(x, p.x); y = MAX(y, p.y); z = MAX(z, p.z); return *this; } + + //! Clamps each element + inline_ Point& Clamp(float min, float max) + { + if(xmax) x=max; + if(ymax) y=max; + if(zmax) z=max; + return *this; + } + + //! Computes square magnitude + inline_ float SquareMagnitude() const { return x*x + y*y + z*z; } + //! Computes magnitude + inline_ float Magnitude() const { return sqrtf(x*x + y*y + z*z); } + //! Computes volume + inline_ float Volume() const { return x * y * z; } + + //! Checks the point is near zero + inline_ bool ApproxZero() const { return SquareMagnitude() < EPSILON2; } + + //! Tests for exact zero vector + inline_ BOOL IsZero() const + { + if(IR(x) || IR(y) || IR(z)) return FALSE; + return TRUE; + } + + //! Checks point validity + inline_ BOOL IsValid() const + { + if(!IsValidFloat(x)) return FALSE; + if(!IsValidFloat(y)) return FALSE; + if(!IsValidFloat(z)) return FALSE; + return TRUE; + } + + //! Slighty moves the point + void Tweak(udword coord_mask, udword tweak_mask) + { + if(coord_mask&1) { udword Dummy = IR(x); Dummy^=tweak_mask; x = FR(Dummy); } + if(coord_mask&2) { udword Dummy = IR(y); Dummy^=tweak_mask; y = FR(Dummy); } + if(coord_mask&4) { udword Dummy = IR(z); Dummy^=tweak_mask; z = FR(Dummy); } + } + + #define TWEAKMASK 0x3fffff + #define TWEAKNOTMASK ~TWEAKMASK + //! Slighty moves the point out + inline_ void TweakBigger() + { + udword Dummy = (IR(x)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(x)) Dummy+=TWEAKMASK+1; x = FR(Dummy); + Dummy = (IR(y)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(y)) Dummy+=TWEAKMASK+1; y = FR(Dummy); + Dummy = (IR(z)&TWEAKNOTMASK); if(!IS_NEGATIVE_FLOAT(z)) Dummy+=TWEAKMASK+1; z = FR(Dummy); + } + + //! Slighty moves the point in + inline_ void TweakSmaller() + { + udword Dummy = (IR(x)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(x)) Dummy+=TWEAKMASK+1; x = FR(Dummy); + Dummy = (IR(y)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(y)) Dummy+=TWEAKMASK+1; y = FR(Dummy); + Dummy = (IR(z)&TWEAKNOTMASK); if(IS_NEGATIVE_FLOAT(z)) Dummy+=TWEAKMASK+1; z = FR(Dummy); + } + + //! Normalizes the vector + inline_ Point& Normalize() + { + float M = x*x + y*y + z*z; + if(M) + { + M = 1.0f / sqrtf(M); + x *= M; + y *= M; + z *= M; + } + return *this; + } + + //! Sets vector length + inline_ Point& SetLength(float length) + { + float NewLength = length / Magnitude(); + x *= NewLength; + y *= NewLength; + z *= NewLength; + return *this; + } + + //! Clamps vector length + inline_ Point& ClampLength(float limit_length) + { + if(limit_length>=0.0f) // Magnitude must be positive + { + float CurrentSquareLength = SquareMagnitude(); + + if(CurrentSquareLength > limit_length * limit_length) + { + float Coeff = limit_length / sqrtf(CurrentSquareLength); + x *= Coeff; + y *= Coeff; + z *= Coeff; + } + } + return *this; + } + + //! Computes distance to another point + inline_ float Distance(const Point& b) const + { + return sqrtf((x - b.x)*(x - b.x) + (y - b.y)*(y - b.y) + (z - b.z)*(z - b.z)); + } + + //! Computes square distance to another point + inline_ float SquareDistance(const Point& b) const + { + return ((x - b.x)*(x - b.x) + (y - b.y)*(y - b.y) + (z - b.z)*(z - b.z)); + } + + //! Dot product dp = this|a + inline_ float Dot(const Point& p) const { return p.x * x + p.y * y + p.z * z; } + + //! Cross product this = a x b + inline_ Point& Cross(const Point& a, const Point& 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; + } + + //! Vector code ( bitmask = sign(z) | sign(y) | sign(x) ) + inline_ udword VectorCode() const + { + return (IR(x)>>31) | ((IR(y)&SIGN_BITMASK)>>30) | ((IR(z)&SIGN_BITMASK)>>29); + } + + //! Returns largest axis + inline_ PointComponent LargestAxis() const + { + const float* Vals = &x; + PointComponent m = _X; + if(Vals[_Y] > Vals[m]) m = _Y; + if(Vals[_Z] > Vals[m]) m = _Z; + return m; + } + + //! Returns closest axis + inline_ PointComponent ClosestAxis() const + { + const float* Vals = &x; + PointComponent m = _X; + if(AIR(Vals[_Y]) > AIR(Vals[m])) m = _Y; + if(AIR(Vals[_Z]) > AIR(Vals[m])) m = _Z; + return m; + } + + //! Returns smallest axis + inline_ PointComponent SmallestAxis() const + { + const float* Vals = &x; + PointComponent m = _X; + if(Vals[_Y] < Vals[m]) m = _Y; + if(Vals[_Z] < Vals[m]) m = _Z; + return m; + } + + //! Refracts the point + Point& Refract(const Point& eye, const Point& n, float refractindex, Point& refracted); + + //! Projects the point onto a plane + Point& ProjectToPlane(const Plane& p); + + //! Projects the point onto the screen + void ProjectToScreen(float halfrenderwidth, float halfrenderheight, const Matrix4x4& mat, HPoint& projected) const; + + //! Unfolds the point onto a plane according to edge(a,b) + Point& Unfold(Plane& p, Point& a, Point& b); + + //! Hash function from Ville Miettinen + inline_ udword GetHashValue() const + { + const udword* h = (const udword*)(this); + udword f = (h[0]+h[1]*11-(h[2]*17)) & 0x7fffffff; // avoid problems with +-0 + return (f>>22)^(f>>12)^(f); + } + + //! Stuff magic values in the point, marking it as explicitely not used. + void SetNotUsed(); + //! Checks the point is marked as not used + BOOL IsNotUsed() const; + + // Arithmetic operators + + //! Unary operator for Point Negate = - Point + inline_ Point operator-() const { return Point(-x, -y, -z); } + + //! Operator for Point Plus = Point + Point. + inline_ Point operator+(const Point& p) const { return Point(x + p.x, y + p.y, z + p.z); } + //! Operator for Point Minus = Point - Point. + inline_ Point operator-(const Point& p) const { return Point(x - p.x, y - p.y, z - p.z); } + + //! Operator for Point Mul = Point * Point. + inline_ Point operator*(const Point& p) const { return Point(x * p.x, y * p.y, z * p.z); } + //! Operator for Point Scale = Point * float. + inline_ Point operator*(float s) const { return Point(x * s, y * s, z * s ); } + //! Operator for Point Scale = float * Point. + inline_ friend Point operator*(float s, const Point& p) { return Point(s * p.x, s * p.y, s * p.z); } + + //! Operator for Point Div = Point / Point. + inline_ Point operator/(const Point& p) const { return Point(x / p.x, y / p.y, z / p.z); } + //! Operator for Point Scale = Point / float. + inline_ Point operator/(float s) const { s = 1.0f / s; return Point(x * s, y * s, z * s); } + //! Operator for Point Scale = float / Point. + inline_ friend Point operator/(float s, const Point& p) { return Point(s / p.x, s / p.y, s / p.z); } + + //! Operator for float DotProd = Point | Point. + inline_ float operator|(const Point& p) const { return x*p.x + y*p.y + z*p.z; } + //! Operator for Point VecProd = Point ^ Point. + inline_ Point operator^(const Point& p) const + { + return Point( + y * p.z - z * p.y, + z * p.x - x * p.z, + x * p.y - y * p.x ); + } + + //! Operator for Point += Point. + inline_ Point& operator+=(const Point& p) { x += p.x; y += p.y; z += p.z; return *this; } + //! Operator for Point += float. + inline_ Point& operator+=(float s) { x += s; y += s; z += s; return *this; } + + //! Operator for Point -= Point. + inline_ Point& operator-=(const Point& p) { x -= p.x; y -= p.y; z -= p.z; return *this; } + //! Operator for Point -= float. + inline_ Point& operator-=(float s) { x -= s; y -= s; z -= s; return *this; } + + //! Operator for Point *= Point. + inline_ Point& operator*=(const Point& p) { x *= p.x; y *= p.y; z *= p.z; return *this; } + //! Operator for Point *= float. + inline_ Point& operator*=(float s) { x *= s; y *= s; z *= s; return *this; } + + //! Operator for Point /= Point. + inline_ Point& operator/=(const Point& p) { x /= p.x; y /= p.y; z /= p.z; return *this; } + //! Operator for Point /= float. + inline_ Point& operator/=(float s) { s = 1.0f/s; x *= s; y *= s; z *= s; return *this; } + + // Logical operators + + //! Operator for "if(Point==Point)" + inline_ bool operator==(const Point& p) const { return ( (IR(x)==IR(p.x))&&(IR(y)==IR(p.y))&&(IR(z)==IR(p.z))); } + //! Operator for "if(Point!=Point)" + inline_ bool operator!=(const Point& p) const { return ( (IR(x)!=IR(p.x))||(IR(y)!=IR(p.y))||(IR(z)!=IR(p.z))); } + + // Arithmetic operators + + //! Operator for Point Mul = Point * Matrix3x3. + inline_ Point operator*(const Matrix3x3& mat) const + { + class ShadowMatrix3x3{ public: float m[3][3]; }; // To allow inlining + const ShadowMatrix3x3* Mat = (const ShadowMatrix3x3*)&mat; + + return Point( + x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0], + x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1], + x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] ); + } + + //! Operator for Point Mul = Point * Matrix4x4. + inline_ Point operator*(const Matrix4x4& mat) const + { + class ShadowMatrix4x4{ public: float m[4][4]; }; // To allow inlining + const ShadowMatrix4x4* Mat = (const ShadowMatrix4x4*)&mat; + + return Point( + x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0] + Mat->m[3][0], + x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1] + Mat->m[3][1], + x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] + Mat->m[3][2]); + } + + //! Operator for Point *= Matrix3x3. + inline_ Point& operator*=(const Matrix3x3& mat) + { + class ShadowMatrix3x3{ public: float m[3][3]; }; // To allow inlining + const ShadowMatrix3x3* Mat = (const ShadowMatrix3x3*)&mat; + + float xp = x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0]; + float yp = x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1]; + float zp = x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2]; + + x = xp; y = yp; z = zp; + + return *this; + } + + //! Operator for Point *= Matrix4x4. + inline_ Point& operator*=(const Matrix4x4& mat) + { + class ShadowMatrix4x4{ public: float m[4][4]; }; // To allow inlining + const ShadowMatrix4x4* Mat = (const ShadowMatrix4x4*)&mat; + + float xp = x * Mat->m[0][0] + y * Mat->m[1][0] + z * Mat->m[2][0] + Mat->m[3][0]; + float yp = x * Mat->m[0][1] + y * Mat->m[1][1] + z * Mat->m[2][1] + Mat->m[3][1]; + float zp = x * Mat->m[0][2] + y * Mat->m[1][2] + z * Mat->m[2][2] + Mat->m[3][2]; + + x = xp; y = yp; z = zp; + + return *this; + } + + // Cast operators + + //! Cast a Point to a HPoint. w is set to zero. + operator HPoint() const; + + inline_ operator const float*() const { return &x; } + inline_ operator float*() { return &x; } + + public: + float x, y, z; + }; + + FUNCTION ICEMATHS_API void Normalize1(Point& a); + FUNCTION ICEMATHS_API void Normalize2(Point& a); + +#endif //__ICEPOINT_H__ diff --git a/Opcode/Ice/IcePreprocessor.h b/Opcode/Ice/IcePreprocessor.h new file mode 100644 index 0000000..bb0ef7b --- /dev/null +++ b/Opcode/Ice/IcePreprocessor.h @@ -0,0 +1,128 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains preprocessor stuff. This should be the first included header. + * \file IcePreprocessor.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICEPREPROCESSOR_H__ +#define __ICEPREPROCESSOR_H__ + + // Check platform + #if defined( _WIN32 ) || defined( WIN32 ) + #pragma message("Compiling on Windows...") + #define PLATFORM_WINDOWS + #else + #pragma message("Compiling on unknown platform...") + #endif + + // Check compiler + #if defined(_MSC_VER) + #pragma message("Compiling with VC++...") + #define COMPILER_VISUAL_CPP + #else + #pragma message("Compiling with unknown compiler...") + #endif + + // Check compiler options. If this file is included in user-apps, this + // shouldn't be needed, so that they can use what they like best. + #ifndef ICE_DONT_CHECK_COMPILER_OPTIONS + #ifdef COMPILER_VISUAL_CPP + #if defined(_CHAR_UNSIGNED) + #endif + + #if defined(_CPPRTTI) + #error Please disable RTTI... + #endif + + #if defined(_CPPUNWIND) + #error Please disable exceptions... + #endif + + #if defined(_MT) + // Multithreading + #endif + #endif + #endif + + // Check debug mode + #ifdef DEBUG // May be defined instead of _DEBUG. Let's fix it. + #ifndef _DEBUG + #define _DEBUG + #endif + #endif + + #ifdef _DEBUG + // Here you may define items for debug builds + #endif + + #ifndef THIS_FILE + #define THIS_FILE __FILE__ + #endif + + #ifndef ICE_NO_DLL + #ifdef ICECORE_EXPORTS + #define ICECORE_API __declspec(dllexport) + #else + #define ICECORE_API __declspec(dllimport) + #endif + #else + #define ICECORE_API + #endif + + // Don't override new/delete +// #define DEFAULT_NEWDELETE + #define DONT_TRACK_MEMORY_LEAKS + + #define FUNCTION extern "C" + + // Cosmetic stuff [mainly useful with multiple inheritance] + #define override(base_class) virtual + + // Our own inline keyword, so that: + // - we can switch to __forceinline to check it's really better or not + // - we can remove __forceinline if the compiler doesn't support it +// #define inline_ __forceinline +// #define inline_ inline + + // Contributed by Bruce Mitchener + #if defined(COMPILER_VISUAL_CPP) + #define inline_ __forceinline +// #define inline_ inline + #elif defined(__GNUC__) && __GNUC__ < 3 + #define inline_ inline + #elif defined(__GNUC__) + #define inline_ inline __attribute__ ((always_inline)) + #else + #define inline_ inline + #endif + + // Down the hatch + #pragma inline_depth( 255 ) + + #ifdef COMPILER_VISUAL_CPP + #pragma intrinsic(memcmp) + #pragma intrinsic(memcpy) + #pragma intrinsic(memset) + #pragma intrinsic(strcat) + #pragma intrinsic(strcmp) + #pragma intrinsic(strcpy) + #pragma intrinsic(strlen) + #pragma intrinsic(abs) + #pragma intrinsic(labs) + #endif + + // ANSI compliance + #ifdef _DEBUG + // Remove painful warning in debug + inline_ bool __False__(){ return false; } + #define for if(__False__()){} else for + #else + #define for if(0){} else for + #endif + +#endif // __ICEPREPROCESSOR_H__ diff --git a/Opcode/Ice/IceRandom.cpp b/Opcode/Ice/IceRandom.cpp new file mode 100644 index 0000000..0139be6 --- /dev/null +++ b/Opcode/Ice/IceRandom.cpp @@ -0,0 +1,35 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for random generators. + * \file IceRandom.cpp + * \author Pierre Terdiman + * \date August, 9, 2001 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceCore; + +void IceCore:: SRand(udword seed) +{ + srand(seed); +} + +udword IceCore::Rand() +{ + return rand(); +} + + +static BasicRandom gRandomGenerator(42); + +udword IceCore::GetRandomIndex(udword max_index) +{ + // We don't use rand() since it's limited to RAND_MAX + udword Index = gRandomGenerator.Randomize(); + return Index % max_index; +} + diff --git a/Opcode/Ice/IceRandom.h b/Opcode/Ice/IceRandom.h new file mode 100644 index 0000000..3584769 --- /dev/null +++ b/Opcode/Ice/IceRandom.h @@ -0,0 +1,42 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for random generators. + * \file IceRandom.h + * \author Pierre Terdiman + * \date August, 9, 2001 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICERANDOM_H__ +#define __ICERANDOM_H__ + + FUNCTION ICECORE_API void SRand(udword seed); + FUNCTION ICECORE_API udword Rand(); + + //! Returns a unit random floating-point value + inline_ float UnitRandomFloat() { return float(Rand()) * ONE_OVER_RAND_MAX; } + + //! Returns a random index so that 0<= index < max_index + ICECORE_API udword GetRandomIndex(udword max_index); + + class ICECORE_API BasicRandom + { + public: + + //! Constructor + inline_ BasicRandom(udword seed=0) : mRnd(seed) {} + //! Destructor + inline_ ~BasicRandom() {} + + inline_ void SetSeed(udword seed) { mRnd = seed; } + inline_ udword GetCurrentValue() const { return mRnd; } + inline_ udword Randomize() { mRnd = mRnd * 2147001325 + 715136305; return mRnd; } + + private: + udword mRnd; + }; + +#endif // __ICERANDOM_H__ + diff --git a/Opcode/Ice/IceRay.cpp b/Opcode/Ice/IceRay.cpp new file mode 100644 index 0000000..be04043 --- /dev/null +++ b/Opcode/Ice/IceRay.cpp @@ -0,0 +1,84 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for rays. + * \file IceRay.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Ray class. + * A ray is a half-line P(t) = mOrig + mDir * t, with 0 <= t <= +infinity + * \class Ray + * \author Pierre Terdiman + * \version 1.0 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/* + O = Origin = impact point + i = normalized vector along the x axis + j = normalized vector along the y axis = actually the normal vector in O + D = Direction vector, norm |D| = 1 + N = Projection of D on y axis, norm |N| = normal reaction + T = Projection of D on x axis, norm |T| = tangential reaction + R = Reflexion vector + + ^y + | + | + | + _ _ _| _ _ _ + * * *| + \ | / + \ |N / | + R\ | /D + \ | / | + \ | / + _________\|/______*_______>x + O T + + Let define theta = angle between D and N. Then cos(theta) = |N| / |D| = |N| since D is normalized. + + j|D = |j|*|D|*cos(theta) => |N| = j|D + + Then we simply have: + + D = N + T + + To compute tangential reaction : + + T = D - N + + To compute reflexion vector : + + R = N - T = N - (D-N) = 2*N - D +*/ + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +float Ray::SquareDistance(const Point& point, float* t) const +{ + Point Diff = point - mOrig; + float fT = Diff | mDir; + + if(fT<=0.0f) + { + fT = 0.0f; + } + else + { + fT /= mDir.SquareMagnitude(); + Diff -= fT*mDir; + } + + if(t) *t = fT; + + return Diff.SquareMagnitude(); +} diff --git a/Opcode/Ice/IceRay.h b/Opcode/Ice/IceRay.h new file mode 100644 index 0000000..f99a78b --- /dev/null +++ b/Opcode/Ice/IceRay.h @@ -0,0 +1,98 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for rays. + * \file IceRay.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICERAY_H__ +#define __ICERAY_H__ + + class ICEMATHS_API Ray + { + public: + //! Constructor + inline_ Ray() {} + //! Constructor + inline_ Ray(const Point& orig, const Point& dir) : mOrig(orig), mDir(dir) {} + //! Copy constructor + inline_ Ray(const Ray& ray) : mOrig(ray.mOrig), mDir(ray.mDir) {} + //! Destructor + inline_ ~Ray() {} + + float SquareDistance(const Point& point, float* t=null) const; + inline_ float Distance(const Point& point, float* t=null) const { return sqrtf(SquareDistance(point, t)); } + + Point mOrig; //!< Ray origin + Point mDir; //!< Normalized direction + }; + + inline_ void ComputeReflexionVector(Point& reflected, const Point& incoming_dir, const Point& outward_normal) + { + reflected = incoming_dir - outward_normal * 2.0f * (incoming_dir|outward_normal); + } + + inline_ void ComputeReflexionVector(Point& reflected, const Point& source, const Point& impact, const Point& normal) + { + Point V = impact - source; + reflected = V - normal * 2.0f * (V|normal); + } + + inline_ void DecomposeVector(Point& normal_compo, Point& tangent_compo, const Point& outward_dir, const Point& outward_normal) + { + normal_compo = outward_normal * (outward_dir|outward_normal); + tangent_compo = outward_dir - normal_compo; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Transforms a direction vector from world space to local space + * \param local_dir [out] direction vector in local space + * \param world_dir [in] direction vector in world space + * \param world [in] world transform + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void ComputeLocalDirection(Point& local_dir, const Point& world_dir, const Matrix4x4& world) + { + // Get world direction back in local space +// Matrix3x3 InvWorld = world; +// local_dir = InvWorld * world_dir; + local_dir = Matrix3x3(world) * world_dir; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Transforms a position vector from world space to local space + * \param local_pt [out] position vector in local space + * \param world_pt [in] position vector in world space + * \param world [in] world transform + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void ComputeLocalPoint(Point& local_pt, const Point& world_pt, const Matrix4x4& world) + { + // Get world vertex back in local space + Matrix4x4 InvWorld = world; + InvWorld.Invert(); + local_pt = world_pt * InvWorld; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Transforms a ray from world space to local space + * \param local_ray [out] ray in local space + * \param world_ray [in] ray in world space + * \param world [in] world transform + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void ComputeLocalRay(Ray& local_ray, const Ray& world_ray, const Matrix4x4& world) + { + // Get world ray back in local space + ComputeLocalDirection(local_ray.mDir, world_ray.mDir, world); + ComputeLocalPoint(local_ray.mOrig, world_ray.mOrig, world); + } + +#endif // __ICERAY_H__ diff --git a/Opcode/Ice/IceRevisitedRadix.cpp b/Opcode/Ice/IceRevisitedRadix.cpp new file mode 100644 index 0000000..f55b0cf --- /dev/null +++ b/Opcode/Ice/IceRevisitedRadix.cpp @@ -0,0 +1,520 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains source code from the article "Radix Sort Revisited". + * \file IceRevisitedRadix.cpp + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Revisited Radix Sort. + * This is my new radix routine: + * - it uses indices and doesn't recopy the values anymore, hence wasting less ram + * - it creates all the histograms in one run instead of four + * - it sorts words faster than dwords and bytes faster than words + * - it correctly sorts negative floating-point values by patching the offsets + * - it automatically takes advantage of temporal coherence + * - multiple keys support is a side effect of temporal coherence + * - it may be worth recoding in asm... (mainly to use FCOMI, FCMOV, etc) [it's probably memory-bound anyway] + * + * History: + * - 08.15.98: very first version + * - 04.04.00: recoded for the radix article + * - 12.xx.00: code lifting + * - 09.18.01: faster CHECK_PASS_VALIDITY thanks to Mark D. Shattuck (who provided other tips, not included here) + * - 10.11.01: added local ram support + * - 01.20.02: bugfix! In very particular cases the last pass was skipped in the float code-path, leading to incorrect sorting...... + * - 01.02.02: - "mIndices" renamed => "mRanks". That's a rank sorter after all. + * - ranks are not "reset" anymore, but implicit on first calls + * - 07.05.02: - offsets rewritten with one less indirection. + * - 11.03.02: - "bool" replaced with RadixHint enum + * + * \class RadixSort + * \author Pierre Terdiman + * \version 1.4 + * \date August, 15, 1998 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/* +To do: + - add an offset parameter between two input values (avoid some data recopy sometimes) + - unroll ? asm ? + - 11 bits trick & 3 passes as Michael did + - prefetch stuff the day I have a P3 + - make a version with 16-bits indices ? +*/ + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceCore; + +#define INVALIDATE_RANKS mCurrentSize|=0x80000000 +#define VALIDATE_RANKS mCurrentSize&=0x7fffffff +#define CURRENT_SIZE (mCurrentSize&0x7fffffff) +#define INVALID_RANKS (mCurrentSize&0x80000000) + +#define CHECK_RESIZE(n) \ + if(n!=mPreviousSize) \ + { \ + if(n>mCurrentSize) Resize(n); \ + else ResetRanks(); \ + mPreviousSize = n; \ + } + +#define CREATE_HISTOGRAMS(type, buffer) \ + /* Clear counters/histograms */ \ + ZeroMemory(mHistogram, 256*4*sizeof(udword)); \ + \ + /* Prepare to count */ \ + ubyte* p = (ubyte*)input; \ + ubyte* pe = &p[nb*4]; \ + udword* h0= &mHistogram[0]; /* Histogram for first pass (LSB) */ \ + udword* h1= &mHistogram[256]; /* Histogram for second pass */ \ + udword* h2= &mHistogram[512]; /* Histogram for third pass */ \ + udword* h3= &mHistogram[768]; /* Histogram for last pass (MSB) */ \ + \ + bool AlreadySorted = true; /* Optimism... */ \ + \ + if(INVALID_RANKS) \ + { \ + /* Prepare for temporal coherence */ \ + type* Running = (type*)buffer; \ + type PrevVal = *Running; \ + \ + while(p!=pe) \ + { \ + /* Read input buffer in previous sorted order */ \ + type Val = *Running++; \ + /* Check whether already sorted or not */ \ + if(ValCurSize) Resize(nb); + mCurrentSize = nb; + INVALIDATE_RANKS; + } +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Main sort routine. + * This one is for integer values. After the call, mRanks contains a list of indices in sorted order, i.e. in the order you may process your data. + * \param input [in] a list of integer values to sort + * \param nb [in] number of values to sort, must be < 2^31 + * \param hint [in] RADIX_SIGNED to handle negative values, RADIX_UNSIGNED if you know your input buffer only contains positive values + * \return Self-Reference + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +RadixSort& RadixSort::Sort(const udword* input, udword nb, RadixHint hint) +{ + // Checkings + if(!input || !nb || nb&0x80000000) return *this; + + // Stats + mTotalCalls++; + + // Resize lists if needed + CheckResize(nb); + +#ifdef RADIX_LOCAL_RAM + // Allocate histograms & offsets on the stack + udword mHistogram[256*4]; +// udword mOffset[256]; + udword* mLink[256]; +#endif + + // Create histograms (counters). Counters for all passes are created in one run. + // Pros: read input buffer once instead of four times + // Cons: mHistogram is 4Kb instead of 1Kb + // We must take care of signed/unsigned values for temporal coherence.... I just + // have 2 code paths even if just a single opcode changes. Self-modifying code, someone? + if(hint==RADIX_UNSIGNED) { CREATE_HISTOGRAMS(udword, input); } + else { CREATE_HISTOGRAMS(sdword, input); } + + // Compute #negative values involved if needed + udword NbNegativeValues = 0; + if(hint==RADIX_SIGNED) + { + // An efficient way to compute the number of negatives values we'll have to deal with is simply to sum the 128 + // last values of the last histogram. Last histogram because that's the one for the Most Significant Byte, + // responsible for the sign. 128 last values because the 128 first ones are related to positive numbers. + udword* h3= &mHistogram[768]; + for(udword i=128;i<256;i++) NbNegativeValues += h3[i]; // 768 for last histogram, 128 for negative part + } + + // Radix sort, j is the pass number (0=LSB, 3=MSB) + for(udword j=0;j<4;j++) + { + CHECK_PASS_VALIDITY(j); + + // Sometimes the fourth (negative) pass is skipped because all numbers are negative and the MSB is 0xFF (for example). This is + // not a problem, numbers are correctly sorted anyway. + if(PerformPass) + { + // Should we care about negative values? + if(j!=3 || hint==RADIX_UNSIGNED) + { + // Here we deal with positive values only + + // Create offsets +// mOffset[0] = 0; +// for(udword i=1;i<256;i++) mOffset[i] = mOffset[i-1] + CurCount[i-1]; + mLink[0] = mRanks2; + for(udword i=1;i<256;i++) mLink[i] = mLink[i-1] + CurCount[i-1]; + } + else + { + // This is a special case to correctly handle negative integers. They're sorted in the right order but at the wrong place. + + // Create biased offsets, in order for negative numbers to be sorted as well +// mOffset[0] = NbNegativeValues; // First positive number takes place after the negative ones + mLink[0] = &mRanks2[NbNegativeValues]; // First positive number takes place after the negative ones +// for(udword i=1;i<128;i++) mOffset[i] = mOffset[i-1] + CurCount[i-1]; // 1 to 128 for positive numbers + for(udword i=1;i<128;i++) mLink[i] = mLink[i-1] + CurCount[i-1]; // 1 to 128 for positive numbers + + // Fixing the wrong place for negative values +// mOffset[128] = 0; + mLink[128] = mRanks2; +// for(i=129;i<256;i++) mOffset[i] = mOffset[i-1] + CurCount[i-1]; + for(udword i=129;i<256;i++) mLink[i] = mLink[i-1] + CurCount[i-1]; + } + + // Perform Radix Sort + ubyte* InputBytes = (ubyte*)input; + InputBytes += j; + if(INVALID_RANKS) + { +// for(udword i=0;i>24; // Radix byte, same as above. AND is useless here (udword). + // ### cmp to be killed. Not good. Later. +// if(Radix<128) mRanks2[mOffset[Radix]++] = i; // Number is positive, same as above +// else mRanks2[--mOffset[Radix]] = i; // Number is negative, flip the sorting order + if(Radix<128) *mLink[Radix]++ = i; // Number is positive, same as above + else *(--mLink[Radix]) = i; // Number is negative, flip the sorting order + } + VALIDATE_RANKS; + } + else + { + for(udword i=0;i>24; // Radix byte, same as above. AND is useless here (udword). + // ### cmp to be killed. Not good. Later. +// if(Radix<128) mRanks2[mOffset[Radix]++] = mRanks[i]; // Number is positive, same as above +// else mRanks2[--mOffset[Radix]] = mRanks[i]; // Number is negative, flip the sorting order + if(Radix<128) *mLink[Radix]++ = mRanks[i]; // Number is positive, same as above + else *(--mLink[Radix]) = mRanks[i]; // Number is negative, flip the sorting order + } + } + // Swap pointers for next pass. Valid indices - the most recent ones - are in mRanks after the swap. + udword* Tmp = mRanks; mRanks = mRanks2; mRanks2 = Tmp; + } + else + { + // The pass is useless, yet we still have to reverse the order of current list if all values are negative. + if(UniqueVal>=128) + { + if(INVALID_RANKS) + { + // ###Possible? + for(udword i=0;i=SqrLen) + { + fT = 1.0f; + Diff -= Dir; + } + else + { + fT /= SqrLen; + Diff -= fT*Dir; + } + } + + if(t) *t = fT; + + return Diff.SquareMagnitude(); +} diff --git a/Opcode/Ice/IceSegment.h b/Opcode/Ice/IceSegment.h new file mode 100644 index 0000000..3dc8314 --- /dev/null +++ b/Opcode/Ice/IceSegment.h @@ -0,0 +1,55 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for segments. + * \file IceSegment.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICESEGMENT_H__ +#define __ICESEGMENT_H__ + + class ICEMATHS_API Segment + { + public: + //! Constructor + inline_ Segment() {} + //! Constructor + inline_ Segment(const Point& p0, const Point& p1) : mP0(p0), mP1(p1) {} + //! Copy constructor + inline_ Segment(const Segment& seg) : mP0(seg.mP0), mP1(seg.mP1) {} + //! Destructor + inline_ ~Segment() {} + + inline_ const Point& GetOrigin() const { return mP0; } + inline_ Point ComputeDirection() const { return mP1 - mP0; } + inline_ void ComputeDirection(Point& dir) const { dir = mP1 - mP0; } + inline_ float ComputeLength() const { return mP1.Distance(mP0); } + inline_ float ComputeSquareLength() const { return mP1.SquareDistance(mP0); } + + inline_ void SetOriginDirection(const Point& origin, const Point& direction) + { + mP0 = mP1 = origin; + mP1 += direction; + } + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes a point on the segment + * \param pt [out] point on segment + * \param t [in] point's parameter [t=0 => pt = mP0, t=1 => pt = mP1] + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + inline_ void ComputePoint(Point& pt, float t) const { pt = mP0 + t * (mP1 - mP0); } + + float SquareDistance(const Point& point, float* t=null) const; + inline_ float Distance(const Point& point, float* t=null) const { return sqrtf(SquareDistance(point, t)); } + + Point mP0; //!< Start of segment + Point mP1; //!< End of segment + }; + +#endif // __ICESEGMENT_H__ diff --git a/Opcode/Ice/IceTriangle.cpp b/Opcode/Ice/IceTriangle.cpp new file mode 100644 index 0000000..ef89109 --- /dev/null +++ b/Opcode/Ice/IceTriangle.cpp @@ -0,0 +1,286 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a handy triangle class. + * \file IceTriangle.cpp + * \author Pierre Terdiman + * \date January, 17, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "Stdafx.h" + +using namespace IceMaths; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a triangle class. + * + * \class Tri + * \author Pierre Terdiman + * \version 1.0 + * \date 08.15.98 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +static sdword VPlaneSideEps(const Point& v, const Plane& plane, float epsilon) +{ + // Compute distance from current vertex to the plane + float Dist = plane.Distance(v); + // Compute side: + // 1 = the vertex is on the positive side of the plane + // -1 = the vertex is on the negative side of the plane + // 0 = the vertex is on the plane (within epsilon) + return Dist > epsilon ? 1 : Dist < -epsilon ? -1 : 0; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Flips the winding order. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void Triangle::Flip() +{ + Point Tmp = mVerts[1]; + mVerts[1] = mVerts[2]; + mVerts[2] = Tmp; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle area. + * \return the area + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Triangle::Area() const +{ + const Point& p0 = mVerts[0]; + const Point& p1 = mVerts[1]; + const Point& p2 = mVerts[2]; + return ((p0 - p1)^(p0 - p2)).Magnitude() * 0.5f; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle perimeter. + * \return the perimeter + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Triangle::Perimeter() const +{ + const Point& p0 = mVerts[0]; + const Point& p1 = mVerts[1]; + const Point& p2 = mVerts[2]; + return p0.Distance(p1) + + p0.Distance(p2) + + p1.Distance(p2); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle compacity. + * \return the compacity + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Triangle::Compacity() const +{ + float P = Perimeter(); + if(P==0.0f) return 0.0f; + return (4.0f*PI*Area()/(P*P)); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle normal. + * \param normal [out] the computed normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void Triangle::Normal(Point& normal) const +{ + const Point& p0 = mVerts[0]; + const Point& p1 = mVerts[1]; + const Point& p2 = mVerts[2]; + normal = ((p0 - p1)^(p0 - p2)).Normalize(); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle denormalized normal. + * \param normal [out] the computed normal + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void Triangle::DenormalizedNormal(Point& normal) const +{ + const Point& p0 = mVerts[0]; + const Point& p1 = mVerts[1]; + const Point& p2 = mVerts[2]; + normal = ((p0 - p1)^(p0 - p2)); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle center. + * \param center [out] the computed center + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void Triangle::Center(Point& center) const +{ + const Point& p0 = mVerts[0]; + const Point& p1 = mVerts[1]; + const Point& p2 = mVerts[2]; + center = (p0 + p1 + p2)*INV3; +} + +PartVal Triangle::TestAgainstPlane(const Plane& plane, float epsilon) const +{ + bool Pos = false, Neg = false; + + // Loop through all vertices + for(udword i=0;i<3;i++) + { + // Compute side: + sdword Side = VPlaneSideEps(mVerts[i], plane, epsilon); + + if (Side < 0) Neg = true; + else if (Side > 0) Pos = true; + } + + if (!Pos && !Neg) return TRI_ON_PLANE; + else if (Pos && Neg) return TRI_INTERSECT; + else if (Pos && !Neg) return TRI_PLUS_SPACE; + else if (!Pos && Neg) return TRI_MINUS_SPACE; + + // What?! + return TRI_FORCEDWORD; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle moment. + * \param m [out] the moment + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/* +void Triangle::ComputeMoment(Moment& m) +{ + // Compute the area of the triangle + m.mArea = Area(); + + // Compute the centroid + Center(m.mCentroid); + + // Second-order components. Handle zero-area faces. + Point& p = mVerts[0]; + Point& q = mVerts[1]; + Point& r = mVerts[2]; + if(m.mArea==0.0f) + { + // This triangle has zero area. The second order components would be eliminated with the usual formula, so, for the + // sake of robustness we use an alternative form. These are the centroid and second-order components of the triangle's vertices. + m.mCovariance.m[0][0] = (p.x*p.x + q.x*q.x + r.x*r.x); + m.mCovariance.m[0][1] = (p.x*p.y + q.x*q.y + r.x*r.y); + m.mCovariance.m[0][2] = (p.x*p.z + q.x*q.z + r.x*r.z); + m.mCovariance.m[1][1] = (p.y*p.y + q.y*q.y + r.y*r.y); + m.mCovariance.m[1][2] = (p.y*p.z + q.y*q.z + r.y*r.z); + m.mCovariance.m[2][2] = (p.z*p.z + q.z*q.z + r.z*r.z); + m.mCovariance.m[2][1] = m.mCovariance.m[1][2]; + m.mCovariance.m[1][0] = m.mCovariance.m[0][1]; + m.mCovariance.m[2][0] = m.mCovariance.m[0][2]; + } + else + { + const float OneOverTwelve = 1.0f / 12.0f; + m.mCovariance.m[0][0] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.x + p.x*p.x + q.x*q.x + r.x*r.x) * OneOverTwelve; + m.mCovariance.m[0][1] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.y + p.x*p.y + q.x*q.y + r.x*r.y) * OneOverTwelve; + m.mCovariance.m[1][1] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.y + p.y*p.y + q.y*q.y + r.y*r.y) * OneOverTwelve; + m.mCovariance.m[0][2] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.z + p.x*p.z + q.x*q.z + r.x*r.z) * OneOverTwelve; + m.mCovariance.m[1][2] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.z + p.y*p.z + q.y*q.z + r.y*r.z) * OneOverTwelve; + m.mCovariance.m[2][2] = m.mArea * (9.0f * m.mCentroid.z*m.mCentroid.z + p.z*p.z + q.z*q.z + r.z*r.z) * OneOverTwelve; + m.mCovariance.m[2][1] = m.mCovariance.m[1][2]; + m.mCovariance.m[1][0] = m.mCovariance.m[0][1]; + m.mCovariance.m[2][0] = m.mCovariance.m[0][2]; + } +} +*/ + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle's smallest edge length. + * \return the smallest edge length + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Triangle::MinEdgeLength() const +{ + float Min = MAX_FLOAT; + float Length01 = mVerts[0].Distance(mVerts[1]); + float Length02 = mVerts[0].Distance(mVerts[2]); + float Length12 = mVerts[1].Distance(mVerts[2]); + if(Length01 < Min) Min = Length01; + if(Length02 < Min) Min = Length02; + if(Length12 < Min) Min = Length12; + return Min; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the triangle's largest edge length. + * \return the largest edge length + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +float Triangle::MaxEdgeLength() const +{ + float Max = MIN_FLOAT; + float Length01 = mVerts[0].Distance(mVerts[1]); + float Length02 = mVerts[0].Distance(mVerts[2]); + float Length12 = mVerts[1].Distance(mVerts[2]); + if(Length01 > Max) Max = Length01; + if(Length02 > Max) Max = Length02; + if(Length12 > Max) Max = Length12; + return Max; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes a point on the triangle according to the stabbing information. + * \param u,v [in] point's barycentric coordinates + * \param pt [out] point on triangle + * \param nearvtx [out] index of nearest vertex + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void Triangle::ComputePoint(float u, float v, Point& pt, udword* nearvtx) const +{ + // Compute point coordinates + pt = (1.0f - u - v)*mVerts[0] + u*mVerts[1] + v*mVerts[2]; + + // Compute nearest vertex if needed + if(nearvtx) + { + // Compute distance vector + Point d(mVerts[0].SquareDistance(pt), // Distance^2 from vertex 0 to point on the face + mVerts[1].SquareDistance(pt), // Distance^2 from vertex 1 to point on the face + mVerts[2].SquareDistance(pt)); // Distance^2 from vertex 2 to point on the face + + // Get smallest distance + *nearvtx = d.SmallestAxis(); + } +} + +void Triangle::Inflate(float fat_coeff, bool constant_border) +{ + // Compute triangle center + Point TriangleCenter; + Center(TriangleCenter); + + // Don't normalize? + // Normalize => add a constant border, regardless of triangle size + // Don't => add more to big triangles + for(udword i=0;i<3;i++) + { + Point v = mVerts[i] - TriangleCenter; + + if(constant_border) v.Normalize(); + + mVerts[i] += v * fat_coeff; + } +} diff --git a/Opcode/Ice/IceTriangle.h b/Opcode/Ice/IceTriangle.h new file mode 100644 index 0000000..02e03ce --- /dev/null +++ b/Opcode/Ice/IceTriangle.h @@ -0,0 +1,68 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a handy triangle class. + * \file IceTriangle.h + * \author Pierre Terdiman + * \date January, 17, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICETRIANGLE_H__ +#define __ICETRIANGLE_H__ + + // Forward declarations + class Moment; + + // Partitioning values + enum PartVal + { + TRI_MINUS_SPACE = 0, //!< Triangle is in the negative space + TRI_PLUS_SPACE = 1, //!< Triangle is in the positive space + TRI_INTERSECT = 2, //!< Triangle intersects plane + TRI_ON_PLANE = 3, //!< Triangle and plane are coplanar + + TRI_FORCEDWORD = 0x7fffffff + }; + + // A triangle class. + class ICEMATHS_API Triangle + { + public: + //! Constructor + inline_ Triangle() {} + //! Constructor + inline_ Triangle(const Point& p0, const Point& p1, const Point& p2) { mVerts[0]=p0; mVerts[1]=p1; mVerts[2]=p2; } + //! Copy constructor + inline_ Triangle(const Triangle& triangle) + { + mVerts[0] = triangle.mVerts[0]; + mVerts[1] = triangle.mVerts[1]; + mVerts[2] = triangle.mVerts[2]; + } + //! Destructor + inline_ ~Triangle() {} + //! Vertices + Point mVerts[3]; + + // Methods + void Flip(); + float Area() const; + float Perimeter() const; + float Compacity() const; + void Normal(Point& normal) const; + void DenormalizedNormal(Point& normal) const; + void Center(Point& center) const; + inline_ Plane PlaneEquation() const { return Plane(mVerts[0], mVerts[1], mVerts[2]); } + + PartVal TestAgainstPlane(const Plane& plane, float epsilon) const; +// float Distance(Point& cp, Point& cq, Tri& tri); + void ComputeMoment(Moment& m); + float MinEdgeLength() const; + float MaxEdgeLength() const; + void ComputePoint(float u, float v, Point& pt, udword* nearvtx=null) const; + void Inflate(float fat_coeff, bool constant_border); + }; + +#endif // __ICETRIANGLE_H__ diff --git a/Opcode/Ice/IceTrilist.h b/Opcode/Ice/IceTrilist.h new file mode 100644 index 0000000..7a8d9de --- /dev/null +++ b/Opcode/Ice/IceTrilist.h @@ -0,0 +1,61 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for a triangle container. + * \file IceTrilist.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICETRILIST_H__ +#define __ICETRILIST_H__ + + class ICEMATHS_API TriList : public Container + { + public: + // Constructor / Destructor + TriList() {} + ~TriList() {} + + inline_ udword GetNbTriangles() const { return GetNbEntries()/9; } + inline_ Triangle* GetTriangles() const { return (Triangle*)GetEntries(); } + + void AddTri(const Triangle& tri) + { + Add(tri.mVerts[0].x).Add(tri.mVerts[0].y).Add(tri.mVerts[0].z); + Add(tri.mVerts[1].x).Add(tri.mVerts[1].y).Add(tri.mVerts[1].z); + Add(tri.mVerts[2].x).Add(tri.mVerts[2].y).Add(tri.mVerts[2].z); + } + + void AddTri(const Point& p0, const Point& p1, const Point& p2) + { + Add(p0.x).Add(p0.y).Add(p0.z); + Add(p1.x).Add(p1.y).Add(p1.z); + Add(p2.x).Add(p2.y).Add(p2.z); + } + }; + + class ICEMATHS_API TriangleList : public Container + { + public: + // Constructor / Destructor + TriangleList() {} + ~TriangleList() {} + + inline_ udword GetNbTriangles() const { return GetNbEntries()/3; } + inline_ IndexedTriangle* GetTriangles() const { return (IndexedTriangle*)GetEntries();} + + void AddTriangle(const IndexedTriangle& tri) + { + Add(tri.mVRef[0]).Add(tri.mVRef[1]).Add(tri.mVRef[2]); + } + + void AddTriangle(udword vref0, udword vref1, udword vref2) + { + Add(vref0).Add(vref1).Add(vref2); + } + }; + +#endif //__ICETRILIST_H__ diff --git a/Opcode/Ice/IceTypes.h b/Opcode/Ice/IceTypes.h new file mode 100644 index 0000000..dac0a71 --- /dev/null +++ b/Opcode/Ice/IceTypes.h @@ -0,0 +1,157 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains custom types. + * \file IceTypes.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICETYPES_H__ +#define __ICETYPES_H__ + + #define USE_HANDLE_MANAGER + + // Constants + #define PI 3.1415926535897932384626433832795028841971693993751f //!< PI + #define HALFPI 1.57079632679489661923f //!< 0.5 * PI + #define TWOPI 6.28318530717958647692f //!< 2.0 * PI + #define INVPI 0.31830988618379067154f //!< 1.0 / PI + + #define RADTODEG 57.2957795130823208768f //!< 180.0 / PI, convert radians to degrees + #define DEGTORAD 0.01745329251994329577f //!< PI / 180.0, convert degrees to radians + + #define EXP 2.71828182845904523536f //!< e + #define INVLOG2 3.32192809488736234787f //!< 1.0 / log10(2) + #define LN2 0.693147180559945f //!< ln(2) + #define INVLN2 1.44269504089f //!< 1.0f / ln(2) + + #define INV3 0.33333333333333333333f //!< 1/3 + #define INV6 0.16666666666666666666f //!< 1/6 + #define INV7 0.14285714285714285714f //!< 1/7 + #define INV9 0.11111111111111111111f //!< 1/9 + #define INV255 0.00392156862745098039f //!< 1/255 + + #define SQRT2 1.41421356237f //!< sqrt(2) + #define INVSQRT2 0.707106781188f //!< 1 / sqrt(2) + + #define SQRT3 1.73205080757f //!< sqrt(3) + #define INVSQRT3 0.577350269189f //!< 1 / sqrt(3) + + #define null 0 //!< our own NULL pointer + + // Custom types used in ICE + typedef signed char sbyte; //!< sizeof(sbyte) must be 1 + typedef unsigned char ubyte; //!< sizeof(ubyte) must be 1 + typedef signed short sword; //!< sizeof(sword) must be 2 + typedef unsigned short uword; //!< sizeof(uword) must be 2 + typedef signed int sdword; //!< sizeof(sdword) must be 4 + typedef unsigned int udword; //!< sizeof(udword) must be 4 + typedef signed __int64 sqword; //!< sizeof(sqword) must be 8 + typedef unsigned __int64 uqword; //!< sizeof(uqword) must be 8 + typedef float float32; //!< sizeof(float32) must be 4 + typedef double float64; //!< sizeof(float64) must be 4 + + ICE_COMPILE_TIME_ASSERT(sizeof(bool)==1); // ...otherwise things might fail with VC++ 4.2 ! + ICE_COMPILE_TIME_ASSERT(sizeof(ubyte)==1); + ICE_COMPILE_TIME_ASSERT(sizeof(sbyte)==1); + ICE_COMPILE_TIME_ASSERT(sizeof(sword)==2); + ICE_COMPILE_TIME_ASSERT(sizeof(uword)==2); + ICE_COMPILE_TIME_ASSERT(sizeof(udword)==4); + ICE_COMPILE_TIME_ASSERT(sizeof(sdword)==4); + ICE_COMPILE_TIME_ASSERT(sizeof(uqword)==8); + ICE_COMPILE_TIME_ASSERT(sizeof(sqword)==8); + + //! TO BE DOCUMENTED + #define DECLARE_ICE_HANDLE(name) struct name##__ { int unused; }; typedef struct name##__ *name + + typedef udword DynID; //!< Dynamic identifier +#ifdef USE_HANDLE_MANAGER + typedef udword KID; //!< Kernel ID +// DECLARE_ICE_HANDLE(KID); +#else + typedef uword KID; //!< Kernel ID +#endif + typedef udword RTYPE; //!< Relationship-type (!) between owners and references + #define INVALID_ID 0xffffffff //!< Invalid dword ID (counterpart of null pointers) +#ifdef USE_HANDLE_MANAGER + #define INVALID_KID 0xffffffff //!< Invalid Kernel ID +#else + #define INVALID_KID 0xffff //!< Invalid Kernel ID +#endif + #define INVALID_NUMBER 0xDEADBEEF //!< Standard junk value + + // Define BOOL if needed + #ifndef BOOL + typedef int BOOL; //!< Another boolean type. + #endif + + //! Union of a float and a sdword + typedef union { + float f; //!< The float + sdword d; //!< The integer + }scell; + + //! Union of a float and a udword + typedef union { + float f; //!< The float + udword d; //!< The integer + }ucell; + + // Type ranges + #define MAX_SBYTE 0x7f //!< max possible sbyte value + #define MIN_SBYTE 0x80 //!< min possible sbyte value + #define MAX_UBYTE 0xff //!< max possible ubyte value + #define MIN_UBYTE 0x00 //!< min possible ubyte value + #define MAX_SWORD 0x7fff //!< max possible sword value + #define MIN_SWORD 0x8000 //!< min possible sword value + #define MAX_UWORD 0xffff //!< max possible uword value + #define MIN_UWORD 0x0000 //!< min possible uword value + #define MAX_SDWORD 0x7fffffff //!< max possible sdword value + #define MIN_SDWORD 0x80000000 //!< min possible sdword value + #define MAX_UDWORD 0xffffffff //!< max possible udword value + #define MIN_UDWORD 0x00000000 //!< min possible udword value + #define MAX_FLOAT FLT_MAX //!< max possible float value + #define MIN_FLOAT (-FLT_MAX) //!< min possible loat value + #define IEEE_1_0 0x3f800000 //!< integer representation of 1.0 + #define IEEE_255_0 0x437f0000 //!< integer representation of 255.0 + #define IEEE_MAX_FLOAT 0x7f7fffff //!< integer representation of MAX_FLOAT + #define IEEE_MIN_FLOAT 0xff7fffff //!< integer representation of MIN_FLOAT + #define IEEE_UNDERFLOW_LIMIT 0x1a000000 + + #define ONE_OVER_RAND_MAX (1.0f / float(RAND_MAX)) //!< Inverse of the max possible value returned by rand() + + typedef int (__stdcall* PROC)(); //!< A standard procedure call. + typedef bool (*ENUMERATION)(udword value, udword param, udword context); //!< ICE standard enumeration call + typedef void** VTABLE; //!< A V-Table. + + #undef MIN + #undef MAX + #define MIN(a, b) ((a) < (b) ? (a) : (b)) //!< Returns the min value between a and b + #define MAX(a, b) ((a) > (b) ? (a) : (b)) //!< Returns the max value between a and b + #define MAXMAX(a,b,c) ((a) > (b) ? MAX (a,c) : MAX (b,c)) //!< Returns the max value between a, b and c + + template inline_ const T& TMin (const T& a, const T& b) { return b < a ? b : a; } + template inline_ const T& TMax (const T& a, const T& b) { return a < b ? b : a; } + template inline_ void TSetMin (T& a, const T& b) { if(a>b) a = b; } + template inline_ void TSetMax (T& a, const T& b) { if(a> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa); + n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc); + n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0); + n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00); + n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000); + // Etc for larger intergers (64 bits in Java) + // NOTE: the >> operation must be unsigned! (>>> in java) + } + + //! Count the number of '1' bits in a 32 bit word (from Steve Baker's Cute Code Collection) + inline_ udword CountBits(udword n) + { + // This relies of the fact that the count of n bits can NOT overflow + // an n bit interger. EG: 1 bit count takes a 1 bit interger, 2 bit counts + // 2 bit interger, 3 bit count requires only a 2 bit interger. + // So we add all bit pairs, then each nible, then each byte etc... + n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1); + n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2); + n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4); + n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8); + n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16); + // Etc for larger intergers (64 bits in Java) + // NOTE: the >> operation must be unsigned! (>>> in java) + return n; + } + + //! Even faster? + inline_ udword CountBits2(udword bits) + { + bits = bits - ((bits >> 1) & 0x55555555); + bits = ((bits >> 2) & 0x33333333) + (bits & 0x33333333); + bits = ((bits >> 4) + bits) & 0x0F0F0F0F; + return (bits * 0x01010101) >> 24; + } + + //! Spread out bits. EG 00001111 -> 0101010101 + //! 00001010 -> 0100010000 + //! This is used to interleve to intergers to produce a `Morten Key' + //! used in Space Filling Curves (See DrDobbs Journal, July 1999) + //! Order is important. + inline_ void SpreadBits(udword& n) + { + n = ( n & 0x0000ffff) | (( n & 0xffff0000) << 16); + n = ( n & 0x000000ff) | (( n & 0x0000ff00) << 8); + n = ( n & 0x000f000f) | (( n & 0x00f000f0) << 4); + n = ( n & 0x03030303) | (( n & 0x0c0c0c0c) << 2); + n = ( n & 0x11111111) | (( n & 0x22222222) << 1); + } + + // Next Largest Power of 2 + // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm + // that recursively "folds" the upper bits into the lower bits. This process yields a bit vector with + // the same most significant 1 as x, but all 1's below it. Adding 1 to that value yields the next + // largest power of 2. For a 32-bit value: + inline_ udword nlpo2(udword x) + { + x |= (x >> 1); + x |= (x >> 2); + x |= (x >> 4); + x |= (x >> 8); + x |= (x >> 16); + return x+1; + } + + //! Test to see if a number is an exact power of two (from Steve Baker's Cute Code Collection) + inline_ bool IsPowerOfTwo(udword n) { return ((n&(n-1))==0); } + + //! Zero the least significant '1' bit in a word. (from Steve Baker's Cute Code Collection) + inline_ void ZeroLeastSetBit(udword& n) { n&=(n-1); } + + //! Set the least significant N bits in a word. (from Steve Baker's Cute Code Collection) + inline_ void SetLeastNBits(udword& x, udword n) { x|=~(~0<> 31; return (x^y)-y; } + + //!< Alternative min function + inline_ sdword min_(sdword a, sdword b) { sdword delta = b-a; return a + (delta&(delta>>31)); } + + // Determine if one of the bytes in a 4 byte word is zero + inline_ BOOL HasNullByte(udword x) { return ((x + 0xfefefeff) & (~x) & 0x80808080); } + + // To find the smallest 1 bit in a word EG: ~~~~~~10---0 => 0----010---0 + inline_ udword LowestOneBit(udword w) { return ((w) & (~(w)+1)); } +// inline_ udword LowestOneBit_(udword w) { return ((w) & (-(w))); } + + // Most Significant 1 Bit + // Given a binary integer value x, the most significant 1 bit (highest numbered element of a bit set) + // can be computed using a SWAR algorithm that recursively "folds" the upper bits into the lower bits. + // This process yields a bit vector with the same most significant 1 as x, but all 1's below it. + // Bitwise AND of the original value with the complement of the "folded" value shifted down by one + // yields the most significant bit. For a 32-bit value: + inline_ udword msb32(udword x) + { + x |= (x >> 1); + x |= (x >> 2); + x |= (x >> 4); + x |= (x >> 8); + x |= (x >> 16); + return (x & ~(x >> 1)); + } + + /* + "Just call it repeatedly with various input values and always with the same variable as "memory". + The sharpness determines the degree of filtering, where 0 completely filters out the input, and 1 + does no filtering at all. + + I seem to recall from college that this is called an IIR (Infinite Impulse Response) filter. As opposed + to the more typical FIR (Finite Impulse Response). + + Also, I'd say that you can make more intelligent and interesting filters than this, for example filters + that remove wrong responses from the mouse because it's being moved too fast. You'd want such a filter + to be applied before this one, of course." + + (JCAB on Flipcode) + */ + inline_ float FeedbackFilter(float val, float& memory, float sharpness) + { + ASSERT(sharpness>=0.0f && sharpness<=1.0f && "Invalid sharpness value in feedback filter"); + if(sharpness<0.0f) sharpness = 0.0f; + else if(sharpness>1.0f) sharpness = 1.0f; + return memory = val * sharpness + memory * (1.0f - sharpness); + } + + //! If you can guarantee that your input domain (i.e. value of x) is slightly + //! limited (abs(x) must be < ((1<<31u)-32767)), then you can use the + //! following code to clamp the resulting value into [-32768,+32767] range: + inline_ int ClampToInt16(int x) + { +// ASSERT(abs(x) < (int)((1<<31u)-32767)); + + int delta = 32767 - x; + x += (delta>>31) & delta; + delta = x + 32768; + x -= (delta>>31) & delta; + return x; + } + + // Generic functions + template inline_ void TSwap(Type& a, Type& b) { const Type c = a; a = b; b = c; } + template inline_ Type TClamp(const Type& x, const Type& lo, const Type& hi) { return ((xhi) ? hi : x); } + + template inline_ void TSort(Type& a, Type& b) + { + if(a>b) TSwap(a, b); + } + + template inline_ void TSort(Type& a, Type& b, Type& c) + { + if(a>b) TSwap(a, b); + if(b>c) TSwap(b, c); + if(a>b) TSwap(a, b); + if(b>c) TSwap(b, c); + } + + // Prevent nasty user-manipulations (strategy borrowed from Charles Bloom) +// #define PREVENT_COPY(curclass) void operator = (const curclass& object) { ASSERT(!"Bad use of operator ="); } + // ... actually this is better ! + #define PREVENT_COPY(cur_class) private: cur_class(const cur_class& object); cur_class& operator=(const cur_class& object); + + //! TO BE DOCUMENTED + #define OFFSET_OF(Class, Member) (size_t)&(((Class*)0)->Member) + //! TO BE DOCUMENTED + #define ARRAYSIZE(p) (sizeof(p)/sizeof(p[0])) + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Returns the alignment of the input address. + * \fn Alignment() + * \param address [in] address to check + * \return the best alignment (e.g. 1 for odd addresses, etc) + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + FUNCTION ICECORE_API udword Alignment(udword address); + + #define IS_ALIGNED_2(x) ((x&1)==0) + #define IS_ALIGNED_4(x) ((x&3)==0) + #define IS_ALIGNED_8(x) ((x&7)==0) + + inline_ void _prefetch(void const* ptr) { (void)*(char const volatile *)ptr; } + + // Compute implicit coords from an index: + // The idea is to get back 2D coords from a 1D index. + // For example: + // + // 0 1 2 ... nbu-1 + // nbu nbu+1 i ... + // + // We have i, we're looking for the equivalent (u=2, v=1) location. + // i = u + v*nbu + // <=> i/nbu = u/nbu + v + // Since 0 <= u < nbu, u/nbu = 0 (integer) + // Hence: v = i/nbu + // Then we simply put it back in the original equation to compute u = i - v*nbu + inline_ void Compute2DCoords(udword& u, udword& v, udword i, udword nbu) + { + v = i / nbu; + u = i - (v * nbu); + } + + // In 3D: i = u + v*nbu + w*nbu*nbv + // <=> i/(nbu*nbv) = u/(nbu*nbv) + v/nbv + w + // u/(nbu*nbv) is null since u/nbu was null already. + // v/nbv is null as well for the same reason. + // Hence w = i/(nbu*nbv) + // Then we're left with a 2D problem: i' = i - w*nbu*nbv = u + v*nbu + inline_ void Compute3DCoords(udword& u, udword& v, udword& w, udword i, udword nbu, udword nbu_nbv) + { + w = i / (nbu_nbv); + Compute2DCoords(u, v, i - (w * nbu_nbv), nbu); + } + +#endif // __ICEUTILS_H__ -- cgit v1.1