diff options
Diffstat (limited to 'dep/include/g3dlite/G3D')
32 files changed, 1694 insertions, 5 deletions
diff --git a/dep/include/g3dlite/G3D/AABox.h b/dep/include/g3dlite/G3D/AABox.h index f42a0f2fa2d..699a3d94674 100644 --- a/dep/include/g3dlite/G3D/AABox.h +++ b/dep/include/g3dlite/G3D/AABox.h @@ -1,37 +1,51 @@ /** @file AABox.h + Axis-aligned box class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2004-01-10 @edited 2006-02-10 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_AABOX_H #define G3D_AABOX_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/debug.h" #include "G3D/Array.h" + namespace G3D { + /** An axis-aligned box. */ class AABox { private: + /** Optional argument placeholder */ static int dummy; + Vector3 lo; Vector3 hi; + public: + /** Does not initialize the fields */ inline AABox() {} + /** Constructs a zero-area AABox at v. */ inline AABox(const Vector3& v) { lo = hi = v; } + /** Assumes that low is less than or equal to high along each dimension. To have this automatically enforced, use <code>AABox(low.min(high), low.max(high));</code> @@ -39,6 +53,7 @@ public: inline AABox(const Vector3& low, const Vector3& high) { set(low, high); } + /** Assumes that low is less than or equal to high along each dimension. */ inline void set(const Vector3& low, const Vector3& high) { @@ -50,12 +65,15 @@ public: hi = high; } + inline const Vector3& low() const { return lo; } + inline const Vector3& high() const { return hi; } + /** The largest possible finite box. */ @@ -63,20 +81,24 @@ public: static const AABox b = AABox(Vector3::minFinite(), Vector3::maxFinite()); return b; } + static inline const AABox& inf() { static const AABox b = AABox(-Vector3::inf(), Vector3::inf()); return b; } + static inline const AABox& zero() { static const AABox b = AABox(Vector3::zero(), Vector3::zero()); return b; } + /** Returns the centroid of the box. */ inline Vector3 center() const { return (lo + hi) * 0.5; } + /** Distance from corner(0) to the next corner along axis a. */ @@ -84,9 +106,11 @@ public: debugAssert(a < 3); return hi[a] - lo[a]; } + inline Vector3 extent() const { return hi - lo; } + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -96,6 +120,7 @@ public: int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -104,39 +129,47 @@ public: int numPlanes, int32& cullingPlaneIndex = dummy, const uint32 testMask = 0xFFFFFF) const; + /** Splits the box into two AABoxes along the specified axis. low contains the part that was closer to negative infinity along axis, high contains the other part. Either may have zero volume. */ void split(const Vector3::Axis& axis, float location, AABox& low, AABox& high) const; + /** Conservative culling test for up to 32 planes. Returns true if there exists a <CODE>plane[p]</CODE> for which the entire object is in the negative half space (opposite the plane normal). + <CODE>testMask</CODE> and <CODE>childMask</CODE> are used for optimizing bounding volume hierarchies. The version of this method that produces childMask is slower than the version without; it should only be used for parent nodes. + @param cullingPlaneIndex The index of the first plane for which the entire object is in the negative half-space. The function exits early when one plane is found. -1 when the function returns false (i.e. when no plane culls the whole object). + @param testMask If bit <I>p</I> is 0, the bounding volume automatically passes the culling test for <CODE>plane[p]</CODE> (i.e. it is known that the volume is entirely within the positive half space). The function must return false if testMask is 0 and test all planes when testMask is -1 (0xFFFFFFFF). + @param childMask Test mask for the children of this volume. + */ bool culledBy( const Array<Plane>& plane, int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** Conservative culling test that does not produce a mask for children. */ @@ -144,6 +177,7 @@ public: const Array<Plane>& plane, int32& cullingPlaneIndex = dummy, const uint32 testMask = -1) const; + inline bool contains( const Vector3& point) const { return @@ -154,47 +188,62 @@ public: (point.y <= hi.y) && (point.z <= hi.z); } + /** @deprecated */ inline float surfaceArea() const { Vector3 diag = hi - lo; return 2.0f * (diag.x * diag.y + diag.y * diag.z + diag.x * diag.z); } + inline float area() const { return surfaceArea(); } + inline float volume() const { Vector3 diag = hi - lo; return diag.x * diag.y * diag.z; } + Vector3 randomInteriorPoint() const; + Vector3 randomSurfacePoint() const; + /** @deprecated use Box constructor */ class Box toBox() const; + /** Returns true if there is any overlap */ bool intersects(const AABox& other) const; + /** Returns true if there is any overlap. @cite Jim Arvo's algorithm from Graphics Gems II*/ bool intersects(const class Sphere& other) const; + /** Return the intersection of the two boxes */ AABox intersect(const AABox& other) const { Vector3 H = hi.min(other.hi); Vector3 L = lo.max(other.lo).min(H); return AABox(L, H); } + inline unsigned int hashCode() const { return lo.hashCode() + hi.hashCode(); } + inline bool operator==(const AABox& b) const { return (lo == b.lo) && (hi == b.hi); } + inline bool operator!=(const AABox& b) const { return !((lo == b.lo) && (hi == b.hi)); } + void getBounds(AABox& out) const { out = *this; } }; + } + /** Hashing function for use with Table. */ @@ -202,5 +251,6 @@ inline unsigned int hashCode(const G3D::AABox& b) { return b.hashCode(); } + #endif diff --git a/dep/include/g3dlite/G3D/Array.h b/dep/include/g3dlite/G3D/Array.h index d9e90b55a00..f58ee5eeedb 100644 --- a/dep/include/g3dlite/G3D/Array.h +++ b/dep/include/g3dlite/G3D/Array.h @@ -1,14 +1,19 @@ /** @file Array.h + @maintainer Morgan McGuire, graphics3d.com @cite Portions written by Aaron Orenstein, a@orenstein.name + @created 2001-03-11 @edited 2007-05-12 + Copyright 2000-2007, Morgan McGuire. All rights reserved. */ + #ifndef G3D_ARRAY_H #define G3D_ARRAY_H + #include "G3D/platform.h" #include "G3D/debug.h" #include "G3D/System.h" @@ -18,34 +23,44 @@ #endif #include <vector> #include <algorithm> + #ifdef G3D_WIN32 # include <new> + # pragma warning (push) // debug information too long # pragma warning( disable : 4312) # pragma warning( disable : 4786) #endif + namespace G3D { + /** Constant for passing to Array::resize */ const bool DONT_SHRINK_UNDERLYING_ARRAY = false; + /** Constant for Array::sort */ const int SORT_INCREASING = 1; /** Constant for Array::sort */ const int SORT_DECREASING = -1; + /** Dynamic 1D array. + Objects must have a default constructor (constructor that takes no arguments) in order to be used with this template. You will get the error "no appropriate default constructor found" if they do not. + Do not use with objects that overload placement <code>operator new</code>, since the speed of Array is partly due to pooled allocation. + If SSE is defined Arrays allocate the first element aligned to 16 bytes. + Array is highly optimized compared to std::vector. Array operations are less expensive than on std::vector and for large amounts of data, Array consumes only 1.5x the total size of the @@ -63,7 +78,9 @@ const int SORT_DECREASING = -1; safe way to access the underlying data as a flat C array -- Array::getCArray. Although (T*)std::vector::begin() can be used for this purpose, it is not guaranteed to succeed on all platforms. + To serialize an array, see G3D::serialize. + Do not subclass an Array. */ template <class T> @@ -71,8 +88,10 @@ class Array { private: /** 0...num-1 are initialized elements, num...numAllocated-1 are not */ T* data; + int num; int numAllocated; + void init(int n, int a) { debugAssert(n <= a); debugAssert(n >= 0); @@ -85,12 +104,14 @@ private: data = NULL; } } + void _copy(const Array &other) { init(other.num, other.num); for (int i = 0; i < num; i++) { data[i] = other.data[i]; } } + /** Returns true iff address points to an element of this array. Used by append. @@ -99,11 +120,13 @@ private: return (address >= data) && (address < data + num); } + /** Only compiled if you use the sort procedure. */ static bool __cdecl compareGT(const T& a, const T& b) { return a > b; } + /** Allocates a new array of size numAllocated (not a parameter to the method) and then copies at most oldNum elements from the old array to it. Destructors are @@ -111,32 +134,41 @@ private: */ void realloc(int oldNum) { T* oldData = data; + // The allocation is separate from the constructor invocation because we don't want // to pay for the cost of constructors until the newly allocated // elements are actually revealed to the application. They // will be constructed in the resize() method. + data = (T*)System::alignedMalloc(sizeof(T) * numAllocated, 16); + // Call the copy constructors {const int N = iMin(oldNum, numAllocated); const T* end = data + N; T* oldPtr = oldData; for (T* ptr = data; ptr < end; ++ptr, ++oldPtr) { + // Use placement new to invoke the constructor at the location // that we determined. Use the copy constructor to make the assignment. const T* constructed = new (ptr) T(*oldPtr); + (void)constructed; debugAssertM(constructed == ptr, "new returned a different address than the one provided by Array."); }} + // Call destructors on the old array (if there is no destructor, this will compile away) {const T* end = oldData + oldNum; for (T* ptr = oldData; ptr < end; ++ptr) { ptr->~T(); }} + System::alignedFree(oldData); } + public: + /** C++ STL style iterator variable. Call begin() to get the first iterator, pre-increment (++i) the iterator to get to @@ -144,6 +176,7 @@ public: */ typedef T* Iterator; typedef const T* ConstIterator; + /** C++ STL style iterator method. Returns the first iterator element. Do not change the size of the array while iterating. @@ -151,6 +184,7 @@ public: Iterator begin() { return data; } + ConstIterator begin() const { return data; } @@ -161,9 +195,11 @@ public: ConstIterator end() const { return data + num; } + Iterator end() { return data + num; } + /** The array returned is only valid until the next append() or resize call, or the Array is deallocated. @@ -171,6 +207,7 @@ public: T* getCArray() { return data; } + /** The array returned is only valid until the next append() or resize call, or the Array is deallocated. @@ -178,22 +215,26 @@ public: const T* getCArray() const { return data; } + /** Creates a zero length array (no heap allocation occurs until resize). */ Array() { init(0, 0); } + /** Creates an array of size. */ Array(int size) { init(size, size); } + /** Copy constructor */ Array(const Array& other) { _copy(other); } + /** Destructor does not delete() the objects if T is a pointer type (e.g. T = int*) instead, it deletes the <B>pointers themselves</B> and @@ -206,6 +247,7 @@ public: for (int i = 0; i < num; i++) { (data + i)->~T(); } + System::alignedFree(data); // Set to 0 in case this Array is global and gets referenced during app exit data = NULL; @@ -213,6 +255,7 @@ public: numAllocated = 0; } + /** Removes all elements. Use resize(0, false) or fastClear if you want to remove all elements without deallocating the underlying array @@ -221,10 +264,12 @@ public: void clear() { resize(0); } + /** resize(0, false) */ void fastClear() { resize(0, false); } + /** Assignment operator. */ @@ -235,6 +280,7 @@ public: } return *this; } + Array& operator=(const std::vector<T>& other) { resize((int)other.size()); for (int i = 0; i < num; ++i) { @@ -242,12 +288,14 @@ public: } return *this; } + /** Number of elements in the array. */ inline int size() const { return num; } + /** Number of elements in the array. (Same as size; this is just here for convenience). @@ -255,6 +303,7 @@ public: inline int length() const { return size(); } + /** Swaps element index with the last element in the array then shrinks the array by one. @@ -265,6 +314,7 @@ public: data[index] = data[num - 1]; resize(size() - 1); } + /** Resizes, calling the default constructor for newly created objects and shrinking the underlying @@ -273,52 +323,65 @@ public: void resize(int n) { resize(n, true); } + /** Resizes without shrinking the underlying array */ void fastResize(int n) { resize(n, false); } + /** Inserts at the specified index and shifts all other elements up by one. */ void insert(int n, const T& value) { // Add space for the extra element resize(num + 1, false); + for (int i = num - 1; i > n; --i) { data[i] = data[i - 1]; } data[n] = value; } + /** @param shrinkIfNecessary if false, memory will never be reallocated when the array shrinks. This makes resizing much faster but can waste memory. */ void resize(int n, bool shrinkIfNecessary) { int oldNum = num; num = n; + // Call the destructors on newly hidden elements if there are any for (int i = num; i < oldNum; ++i) { (data + i)->~T(); } + // Once allocated, always maintain 10 elements or 32 bytes, whichever is higher. static const int minSize = iMax(10, 32 / sizeof(T)); + if (num > numAllocated) { // Grow the underlying array + if (numAllocated == 0) { // First allocation; grow to exactly the size requested to avoid wasting space. numAllocated = n; debugAssert(oldNum == 0); realloc(oldNum); } else { + if (num < minSize) { // Grow to at least the minimum size numAllocated = minSize; + } else { + // Increase the underlying size of the array. Grow aggressively // up to 64k, less aggressively up to 400k, and then grow relatively // slowly (1.5x per resize) to avoid excessive space consumption. // // These numbers are tweaked according to performance tests. + float growFactor = 3.0; + size_t oldSizeBytes = numAllocated * sizeof(T); if (oldSizeBytes > 400000) { // Avoid bloat @@ -327,19 +390,26 @@ public: // This is what std:: uses at all times growFactor = 2.0; } + numAllocated = (num - numAllocated) + (int)(numAllocated * growFactor); + if (numAllocated < minSize) { numAllocated = minSize; } } + realloc(oldNum); } + } else if ((num <= numAllocated / 3) && shrinkIfNecessary && (num > minSize)) { // Shrink the underlying array + // Only copy over old elements that still remain after resizing // (destructors were called for others if we're shrinking) realloc(iMin(num, oldNum)); + } + // Call the constructors on newly revealed elements. // Do not use parens because we don't want the intializer // invoked for POD types. @@ -347,12 +417,14 @@ public: new (data + i) T; } } + /** Add an element to the end of the array. Will not shrink the underlying array under any circumstances. It is safe to append an element that is already in the array. */ inline void append(const T& value) { + if (num < numAllocated) { // This is a simple situation; just stick it in the next free slot using // the copy constructor. @@ -372,6 +444,7 @@ public: } } + inline void append(const T& v1, const T& v2) { if (inArray(&v1) || inArray(&v2)) { T t1 = v1; @@ -390,6 +463,7 @@ public: } } + inline void append(const T& v1, const T& v2, const T& v3) { if (inArray(&v1) || inArray(&v2) || inArray(&v3)) { T t1 = v1; @@ -411,6 +485,7 @@ public: } } + inline void append(const T& v1, const T& v2, const T& v3, const T& v4) { if (inArray(&v1) || inArray(&v2) || inArray(&v3) || inArray(&v4)) { T t1 = v1; @@ -434,6 +509,7 @@ public: data[num - 1] = v4; } } + /** Returns true if the given element is in the array. */ @@ -443,8 +519,10 @@ public: return true; } } + return false; } + /** Append the elements of array. Cannot be called with this array as an argument. @@ -453,11 +531,14 @@ public: debugAssert(this != &array); int oldNum = num; int arrayLength = array.length(); + resize(num + arrayLength, false); + for (int i = 0; i < arrayLength; i++) { data[oldNum + i] = array.data[i]; } } + /** Pushes a new element onto the end and returns its address. This is the same as A.resize(A.size() + 1, false); A.last() @@ -466,24 +547,29 @@ public: resize(num + 1, false); return last(); } + /** Pushes an element onto the end (appends) */ inline void push(const T& value) { append(value); } + inline void push(const Array<T>& array) { append(array); } + /** Alias to provide std::vector compatibility */ inline void push_back(const T& v) { push(v); } + /** "The member function removes the last element of the controlled sequence, which must be non-empty." For compatibility with std::vector. */ inline void pop_back() { pop(); } + /** "The member function returns the storage currently allocated to hold the controlled sequence, a value at least as large as size()" @@ -492,6 +578,7 @@ public: int capacity() const { return numAllocated; } + /** "The member function returns a reference to the first element of the controlled sequence, which must be non-empty." @@ -500,6 +587,7 @@ public: T& front() { return (*this)[0]; } + /** "The member function returns a reference to the first element of the controlled sequence, which must be non-empty." @@ -508,6 +596,7 @@ public: const T& front() const { return (*this)[0]; } + /** Removes the last element and returns it. By default, shrinks the underlying array. */ @@ -517,6 +606,7 @@ public: resize(num - 1, shrinkUnderlyingArrayIfNecessary); return temp; } + /** Pops the last element and discards it without returning anything. Faster than pop. By default, does not shrink the underlying array.*/ inline void popDiscard(bool shrinkUnderlyingArrayIfNecessary = false) { @@ -524,9 +614,11 @@ public: resize(num - 1, shrinkUnderlyingArrayIfNecessary); } + /** "The member function swaps the controlled sequences between *this and str." Note that this is slower than the optimal std implementation. + For compatibility with std::vector. */ void swap(Array<T>& str) { @@ -535,6 +627,7 @@ public: *this = temp; } + /** Performs bounds checks in debug mode */ @@ -543,10 +636,12 @@ public: debugAssert(data!=NULL); return data[n]; } + inline T& operator[](unsigned int n) { debugAssertM(((int)n < num), format("Array index out of bounds. n = %d, size() = %d", n, num)); return data[n]; } + /** Performs bounds checks in debug mode */ @@ -555,21 +650,25 @@ public: debugAssert(data!=NULL); return data[n]; } + inline const T& operator[](unsigned int n) const { debugAssert((n < (unsigned int)num)); debugAssert(data!=NULL); return data[n]; } + inline T& randomElement() { debugAssert(num > 0); debugAssert(data!=NULL); return data[iRandom(0, num - 1)]; } + inline const T& randomElement() const { debugAssert(num > 0); debugAssert(data!=NULL); return data[iRandom(0, num - 1)]; } + /** Returns the last element, performing a check in debug mode that there is at least one element. @@ -579,45 +678,54 @@ public: debugAssert(data!=NULL); return data[num - 1]; } + /** Returns element lastIndex() */ inline T& last() { debugAssert(num > 0); debugAssert(data!=NULL); return data[num - 1]; } + /** Returns <i>size() - 1</i> */ inline int lastIndex() const { debugAssertM(num > 0, "Array is empty"); return num - 1; } + inline int firstIndex() const { debugAssertM(num > 0, "Array is empty"); return 0; } + /** Returns element firstIndex(), performing a check in debug mode to ensure that there is at least one */ inline T& first() { debugAssertM(num > 0, "Array is empty"); return data[0]; } + inline const T& first() const { debugAssertM(num > 0, "Array is empty"); return data[0]; } + /** Returns iFloor(size() / 2), throws an assertion in debug mode if the array is empty */ inline int middleIndex() const { debugAssertM(num > 0, "Array is empty"); return num >> 1; } + /** Returns element middleIndex() */ inline const T& middle() const { debugAssertM(num > 0, "Array is empty"); return data[num >> 1]; } + /** Returns element middleIndex() */ inline T& middle() { debugAssertM(num > 0, "Array is empty"); return data[num >> 1]; } + /** Calls delete on all objects[0...size-1] and sets the size to zero. @@ -628,6 +736,7 @@ public: } resize(0); } + /** Returns the index of (the first occurance of) an index or -1 if not found. @@ -640,6 +749,7 @@ public: } return -1; } + /** Finds an element and returns the iterator to it. If the element isn't found then returns end(). @@ -652,6 +762,7 @@ public: } return end(); } + ConstIterator find(const T& value) const { for (int i = 0; i < num; ++i) { if (data[i] == value) { @@ -660,6 +771,7 @@ public: } return end(); } + /** Removes count elements from the array referenced either by index or Iterator. @@ -668,22 +780,28 @@ public: debugAssert((element >= begin()) && (element < end())); debugAssert((count > 0) && (element + count) <= end()); Iterator last = end() - count; + while(element < last) { element[0] = element[count]; ++element; } + resize(num - count); } + void remove(int index, int count = 1) { debugAssert((index >= 0) && (index < num)); debugAssert((count > 0) && (index + count <= num)); + remove(begin() + index, count); } + /** Reverse the elements of the array in place. */ void reverse() { T temp; + int n2 = num / 2; for (int i = 0; i < n2; ++i) { temp = data[num - 1 - i]; @@ -691,15 +809,19 @@ public: data[i] = temp; } } + /** Sort using a specific less-than function, e.g.: + <PRE> bool __cdecl myLT(const MyClass& elem1, const MyClass& elem2) { return elem1.x < elem2.x; } </PRE> + Note that for pointer arrays, the <CODE>const</CODE> must come <I>after</I> the class name, e.g., <CODE>Array<MyClass*></CODE> uses: + <PRE> bool __cdecl myLT(MyClass*const& elem1, MyClass*const& elem2) { return elem1->x < elem2->x; @@ -710,6 +832,7 @@ public: std::sort(data, data + num, lessThan); } + /** Sorts the array in increasing order using the > or < operator. To invoke this method on Array<T>, T must override those operator. @@ -730,6 +853,7 @@ public: std::sort(data, data + num, compareGT); } } + /** Sorts elements beginIndex through and including endIndex. */ @@ -740,9 +864,11 @@ public: std::sort(data + beginIndex, data + endIndex + 1, compareGT); } } + void sortSubArray(int beginIndex, int endIndex, bool (__cdecl *lessThan)(const T& elem1, const T& elem2)) { std::sort(data + beginIndex, data + endIndex + 1, lessThan); } + /** The StrictWeakOrdering can be either a class that overloads the function call operator() or a function pointer of the form <code>bool (__cdecl *lessThan)(const T& elem1, const T& elem2)</code> @@ -751,6 +877,7 @@ public: void sortSubArray(int beginIndex, int endIndex, StrictWeakOrdering& lessThan) { std::sort(data + beginIndex, data + endIndex + 1, lessThan); } + /** Uses < and == to evaluate operator(); this is the default comparator for Array::partition. */ class DefaultComparator { public: @@ -764,11 +891,14 @@ public: } } }; + /** The output arrays are resized with fastClear() so that if they are already of the same size as this array no memory is allocated during partitioning. + @param comparator A function, or class instance with an overloaded operator() that compares two elements of type <code>T</code> and returns 0 if they are equal, -1 if the second is smaller, and 1 if the first is smaller (i.e., following the conventions of std::string::compare). For example: + <pre> int compare(int A, int B) { if (A < B) { @@ -788,6 +918,7 @@ public: Array<T>& eqArray, Array<T>& gtArray, const Comparator& comparator) const { + // Make sure all arrays are independent debugAssert(<Array != this); debugAssert(&eqArray != this); @@ -795,19 +926,24 @@ public: debugAssert(<Array != &eqArray); debugAssert(<Array != >Array); debugAssert(&eqArray != >Array); + // Clear the arrays ltArray.fastClear(); eqArray.fastClear(); gtArray.fastClear(); + // Form a table of buckets for lt, eq, and gt Array<T>* bucket[3] = {<Array, &eqArray, >Array}; + for (int i = 0; i < num; ++i) { int c = comparator(partitionElement, data[i]); debugAssertM(c >= -1 && c <= 1, "Comparator returned an illegal value."); + // Insert into the correct bucket, 0, 1, or 2 bucket[c + 1]->append(data[i]); } } + /** Uses < and == on elements to perform a partition. See partition(). */ @@ -816,13 +952,16 @@ public: Array<T>& ltArray, Array<T>& eqArray, Array<T>& gtArray) const { + partition(partitionElement, ltArray, eqArray, gtArray, typename Array<T>::DefaultComparator()); } + /** Paritions the array into those below the median, those above the median, and those elements equal to the median in expected O(n) time using quickselect. If the array has an even number of different elements, the median for partition purposes is the largest value less than the median. + @param tempArray used for working scratch space @param comparator see parition() for a discussion.*/ template<typename Comparator> @@ -832,32 +971,39 @@ public: Array<T>& gtMedian, Array<T>& tempArray, const Comparator& comparator) const { + ltMedian.fastClear(); eqMedian.fastClear(); gtMedian.fastClear(); + // Handle trivial cases first switch (size()) { case 0: // Array is empty; no parition is possible return; + case 1: // One element eqMedian.append(first()); return; + case 2: { // Two element array; median is the smaller int c = comparator(first(), last()); + switch (c) { case -1: // first was bigger eqMedian.append(last()); gtMedian.append(first()); break; + case 0: // Both equal to the median eqMedian.append(first(), last()); break; + case 1: // Last was bigger eqMedian.append(first()); @@ -867,11 +1013,15 @@ public: } return; } + // All other cases use a recursive randomized median + // Number of values less than all in the current arrays int ltBoost = 0; + // Number of values greater than all in the current arrays int gtBoost = 0; + // For even length arrays, force the gt array to be one larger than the // lt array: // [1 2 3] size = 3, choose half = (s + 1) /2 @@ -884,6 +1034,7 @@ public: lowerHalfSize = upperHalfSize = (size() + 1) / 2; } const T* xPtr = NULL; + // Maintain pointers to the arrays; we'll switch these around during sorting // to avoid copies. const Array<T>* source = this; @@ -891,52 +1042,68 @@ public: Array<T>* eq = &eqMedian; Array<T>* gt = >Median; Array<T>* extra = &tempArray; + while (true) { // Choose a random element -- choose the middle element; this is theoretically // suboptimal, but for loosly sorted array is actually the best strategy + xPtr = &(source->middle()); if (source->size() == 1) { // Done; there's only one element left break; } const T& x = *xPtr; + // Note: partition (fast) clears the arrays for us source->partition(x, *lt, *eq, *gt, comparator); + int L = lt->size() + ltBoost + eq->size(); int U = gt->size() + gtBoost + eq->size(); if ((L >= lowerHalfSize) && (U >= upperHalfSize)) { + // x must be the partition median break; + } else if (L < lowerHalfSize) { + // x must be smaller than the median. Recurse into the 'gt' array. ltBoost += lt->size() + eq->size(); + // The new gt array will be the old source array, unless // that was the this pointer (i.e., unless we are on the // first iteration) Array<T>* newGt = (source == this) ? extra : const_cast<Array<T>*>(source); + // Now set up the gt array as the new source source = gt; gt = newGt; + } else { + // x must be bigger than the median. Recurse into the 'lt' array. gtBoost += gt->size() + eq->size(); + // The new lt array will be the old source array, unless // that was the this pointer (i.e., unless we are on the // first iteration) Array<T>* newLt = (source == this) ? extra : const_cast<Array<T>*>(source); + // Now set up the lt array as the new source source = lt; lt = newLt; } } + // Now that we know the median, make a copy of it (since we're about to destroy the array that it // points into). T median = *xPtr; xPtr = NULL; + // Partition the original array (note that this fast clears for us) partition(median, ltMedian, eqMedian, gtMedian, comparator); } + /** Computes a median partition using the default comparator and a dynamically allocated temporary working array. If the median is not in the array, it is chosen to be the largest value smaller @@ -946,24 +1113,30 @@ public: Array<T>& ltMedian, Array<T>& eqMedian, Array<T>& gtMedian) const { + Array<T> temp; medianPartition(ltMedian, eqMedian, gtMedian, temp, DefaultComparator()); } + /** Redistributes the elements so that the new order is statistically independent of the original order. O(n) time.*/ void randomize() { T temp; + for (int i = size() - 1; i >= 0; --i) { int x = iRandom(0, i); + temp = data[i]; data[i] = data[x]; data[x] = temp; } } + }; + /** Array::contains for C-arrays */ template<class T> bool contains(const T* array, int len, const T& e) { for (int i = len - 1; i >= 0; --i) { @@ -973,8 +1146,11 @@ template<class T> bool contains(const T* array, int len, const T& e) { } return false; } + } // namespace + #endif + #ifdef G3D_WIN32 # pragma warning (push) #endif diff --git a/dep/include/g3dlite/G3D/Box.h b/dep/include/g3dlite/G3D/Box.h index fccff258a25..8ec7ea3408d 100644 --- a/dep/include/g3dlite/G3D/Box.h +++ b/dep/include/g3dlite/G3D/Box.h @@ -1,66 +1,92 @@ /** @file Box.h + Box class + @maintainer Morgan McGuire, matrix@graphics3d.com + @cite Portions based on Dave Eberly's Magic Software Library at <A HREF="http://www.magic-software.com">http://www.magic-software.com</A> @created 2001-06-02 @edited 2006-01-05 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_BOX_H #define G3D_BOX_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Array.h" #include "G3D/Plane.h" + namespace G3D { + class CoordinateFrame; + /** An arbitrary 3D box, useful as a bounding box. + To construct a box from a coordinate frame, center and extent, use the idiom: + <CODE>Box box = cframe.toObjectSpace(Box(center - extent/2, center + extent/2));</CODE> */ class Box { private: + static int32 dummy; + friend class CoordinateFrame; + /** <PRE> 3 2 7 6 + 0 1 4 5 + front back (seen through front) </PRE> */ Vector3 _corner[8]; + /** Unit axes. */ Vector3 _axis[3]; + Vector3 _center; + /** Extent along each axis. */ Vector3 _extent; + float _area; float _volume; + void init( const Vector3& min, const Vector3& max); + public: + /** Does not initialize the fields. */ Box(); + /** Constructs a box from two opposite corners. */ Box( const Vector3& min, const Vector3& max); + Box(const class AABox& b); + /** Returns the object to world transformation for this box. localFrame().worldToObject(...) takes @@ -69,16 +95,20 @@ public: is no scaling in this transformation. */ CoordinateFrame localFrame() const; + void getLocalFrame(CoordinateFrame& frame) const; + /** Returns the centroid of the box. */ inline Vector3 center() const { return _center; } + inline Vector3 getCenter() const { return center(); } + /** Returns a corner (0 <= i < 8) @deprecated @@ -87,10 +117,12 @@ public: debugAssert(i < 8); return _corner[i]; } + inline Vector3 corner(int i) const { debugAssert(i < 8); return _corner[i]; } + /** Unit length. */ @@ -98,6 +130,7 @@ public: debugAssert(a < 3); return _axis[a]; } + /** Distance from corner(0) to the next corner along the box's local axis a. @@ -106,9 +139,11 @@ public: debugAssert(a < 3); return (float)_extent[a]; } + inline Vector3 extent() const { return _extent; } + /** Returns the four corners of a face (0 <= f < 6). The corners are returned to form a counter clockwise quad facing outwards. @@ -119,6 +154,7 @@ public: Vector3& v1, Vector3& v2, Vector3& v3) const; + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -128,6 +164,7 @@ public: int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -136,6 +173,7 @@ public: int numPlanes, int32& cullingPlaneIndex = dummy, const uint32 testMask = -1) const; + /** See AABox::culledBy */ @@ -144,6 +182,7 @@ public: int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** Conservative culling test that does not produce a mask for children. */ @@ -151,15 +190,21 @@ public: const Array<Plane>& plane, int32& cullingPlaneIndex = dummy, const uint32 testMask = -1) const; + bool contains( const Vector3& point) const; + /** @deprecated */ float surfaceArea() const; + inline float area() const { return surfaceArea(); } + float volume() const; + void getRandomSurfacePoint(Vector3& P, Vector3& N = Vector3::dummy) const; + /** @deprecated Uniformly distributed on the surface. @@ -169,12 +214,16 @@ public: getRandomSurfacePoint(V); return V; } + /** Uniformly distributed on the interior (includes surface) */ Vector3 randomInteriorPoint() const; + void getBounds(class AABox&) const; }; + } + #endif diff --git a/dep/include/g3dlite/G3D/CollisionDetection.h b/dep/include/g3dlite/G3D/CollisionDetection.h index ee4683771a4..4add967ed8b 100644 --- a/dep/include/g3dlite/G3D/CollisionDetection.h +++ b/dep/include/g3dlite/G3D/CollisionDetection.h @@ -1,20 +1,26 @@ /** @file CollisionDetection.h + Moving collision detection for simple primitives. + @author Morgan McGuire, matrix@graphics3d.com @cite Spherical collision based on Paul Nettle's ftp://ftp.3dmaileffects.com/pub/FluidStudios/CollisionDetection/Fluid_Studios_Generic_Collision_Detection_for_Games_Using_Ellipsoids.pdf and comments by Max McGuire. Ray-sphere intersection by Eric Haines. Box-Box intersection written by Kevin Egan. Thanks to Max McGuire of Iron Lore for various bug fixes. + @created 2001-11-19 @edited 2006-01-10 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_COLLISIONDETECTION_H #define G3D_COLLISIONDETECTION_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Plane.h" @@ -23,15 +29,19 @@ #include "G3D/Array.h" #include "G3D/Ray.h" #include "G3D/Line.h" + namespace G3D { + /** Collision detection primitives and tools for building higher order collision detection schemes. + These routines provide <I>moving</I> and static collision detection. Moving collision detection allows the calculation of collisions that occur during a period of time -- as opposed to the intersection of two static bodies. + Moving collision detection routines detect collisions between <I>only</I> static primitives and moving spheres or points. Since the reference frame can be user defined, these functions can be used to @@ -39,18 +49,23 @@ namespace G3D { the velocity vector of one object from the velocity vector of the sphere or point the detection is to occur with. This unified velocity vector will act as if both objects are moving simultaneously. + Collisions are detected for single-sided objects only. That is, no collision is detected when <I>leaving</I> a primitive or passing through a plane or triangle opposite the normal... except for the point-sphere calculation or when otherwise noted. + For a sphere, the collision location returned is the point in world space where the surface of the sphere and the fixed object meet. It is <B>not</B> the position of the center of the sphere at the time of the collision. + The collision normal returned is the surface normal to the fixed object at the collision location. + <p> <b>Static Collision Detection:</b> (Neither object is moving) + <table> <tr><td></td><td><b>Vector3</b></td><td><b>LineSegment</b></td><td><b>Ray *</b></td><td><b>Line</b></td><td><b>Plane</b></td><td><b>Triangle</b></td><td><b>Sphere</b></td><td><b>Cylinder</b></td><td><b>Capsule</b></td><td><b>AABox</b></td><td><b>Box</b></td></tr> <tr><td><b>Vector3</b></td><td>Vector3::operator== Vector3::fuzzyEq G3D::distance</td><td bgcolor=#C0C0C0 colspan=10 ></td></tr> @@ -65,56 +80,69 @@ namespace G3D { <tr><td><b>AABox</b></td><td>AABox::contains</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=1 ></td></tr> <tr><td><b>Box</b></td><td>Box::contains</td><td>(treat as Ray)</td><td>CollisionDetection::collisionTimeForMovingPointFixedBox</td><td>(treat as Ray)</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedPlane</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedPlane</td><td>CollisionDetection::penetrationDepthForFixedSphereFixedBox</td><td>None (use OPCODE)</td><td>CollisionDetection::movingSpherePassesThroughFixedBox</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedBox</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedBox</td></tr> </table> + <p> <b>Moving Collision Detection:</b> + <i>* Note: Moving collision detection against certain primitives is equivalent to static collision detection against a bigger primitive. Ray, Line Segment == ``moving Point''; Capsule ==``moving Sphere''; Plane == ``moving Line''</i> */ class CollisionDetection { private: + /** Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function. */ static Vector3 ignore; + /** Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function. */ static bool ignoreBool; + /** Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function. */ static Array<Vector3> ignoreArray; + // Static class! CollisionDetection() {} virtual ~CollisionDetection() {} + public: + /** Converts an index [0, 15] to the corresponding separating axis. Does not return normalized vector in the edge-edge case (indices 6 through 15). + @param separatingAxisIndex Separating axis. @param box1 Box 1. @param box2 Box 2. + @return Axis that separates the two boxes. */ static Vector3 separatingAxisForSolidBoxSolidBox( const int separatingAxisIndex, const Box & box1, const Box & box2); + /** Tests whether two boxes have axes that are parallel to each other. If they are, axis1 and axis2 are set to be the parallel axes for both box1 and box2 respectively. + @param ca Dot products of each of the boxes axes @param epsilon Fudge factor (small unit by which the dot products may vary and still be considered zero). @param axis1 Parallel Axis 1. [Post Condition] @param axis2 Parallel Axis 2. [Post Condition] + @return true - If boxes have a parallel axis @return false - otherwise. */ @@ -123,12 +151,14 @@ public: const double epsilon, int & axis1, int & axis2); + /** Calculates the projected distance between the two boxes along the specified separating axis, negative distances correspond to an overlap along that separating axis. The distance is not divided by denominator dot(L, L), see penetrationDepthForFixedSphereFixedBox() for more details + @param separatingAxisIndex @param a Box 1's bounding sphere vector @param b Box 2's bounding sphere vector @@ -139,6 +169,7 @@ public: of Box 1 and Box 2. @param ad Pointer to array of dot products of Box 1 axes and D. @param bd Pointer to array of dot products of Box 2 axes and D. + @return Projected distance between the two boxes along the specified separating axis. */ @@ -152,6 +183,7 @@ public: const double* ad, const double* bd); + /** Creates a set of standard information about two boxes in order to solve for their collision. This information includes a vector to @@ -161,16 +193,20 @@ public: of both boxes (signed and unsigned values), and the dot products between all the axes of box1 and the boxes' center vector and box2 and the boxes' center vector. + @pre The following space requirements must be met: - c[] 9 elements - ca[] 9 elements - ad[] 3 elements - bd[] 3 elements + @cite dobted from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf + @note Links are out-dated. (Kept to preserve origin and authorship) + @param box1 Box 1 @param box2 Box 2 @param a Box 1's bounding sphere vector @@ -193,15 +229,18 @@ public: double* ca, double* ad, double* bd); + /** Performs a simple bounding sphere check between two boxes to determine whether these boxes could <i>possibly</i> intersect. This is a very cheap operation (three dot products, two sqrts and a few others). If it returns true, an intersection is possible, but not necessarily guaranteed. + @param a Vector from box A's center to an outer vertex @param b Vector from box B's center to an outer vertex @param D Distance between the centers of the two boxes + @return true - if possible intersection @return false - otherwise (This does not guarantee an intersection) */ @@ -209,20 +248,25 @@ public: const Vector3 & a, const Vector3 & b, const Vector3 & D); + /** Determines whether two fixed solid boxes intersect. + @note To speed up collision detection, the lastSeparatingAxis from the previous time step can be passed in and that plane can be checked first. If the separating axis was not saved, or if the two boxes intersected then lastSeparatingAxis should equal -1. + @cite Adobted from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf + @param box1 Box 1. @param box2 Box 2. @param lastSeparatingAxis Last separating axis. (optimization - see note) + @return true - Intersection. @return false - otherwise. */ @@ -230,17 +274,21 @@ public: const Box& box1, const Box& box2, const int lastSeparatingAxis = -1); + /** Calculates the closest points on two lines with each other. If the lines are parallel then using the starting point, else calculate the closest point on each line to the other. + @note This is very similiar to calculating the intersection of two lines. Logically then, the two points calculated would be identical if calculated with inifinite precision, but with the finite precision of floating point calculations, these values could (will) differ as the line slope approaches zero or inifinity. + @cite variables and algorithm based on derivation at the following website: http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm + @param line1 Line 1. @param line2 Line 2. @param closest1 Closest point on line 1. @@ -251,6 +299,7 @@ public: const Line & line2, Vector3 & closest1, Vector3 & closest2); + /** Calculates the depth of penetration between two fixed boxes. Contact normal faces away from box1 and into box2. If there is @@ -262,20 +311,24 @@ public: - if the separating axis corresponds to two edges the contact point is the midpoint of the smallest line segment between the two edge lines + @note This is very similiar to calculating the intersection of two lines. Logically then, the two points calculated would be identical if calculated with inifinite precision, but with the finite precision of floating point calculations, these values could (will) differ as the line slope approaches zero or inifinity. + @cite adobted from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf + @param box1 Box 1 @param box2 Box 2 @param contactPoints Contact point between boxes. [Post Condition] @param contactNormals Surface normal at contact point. [Post Condition] @param lastSeparatingAxis Last separating axis. (Used for optimization) + @return Depth of penetration between the two boxes. If there is no intersection between the boxes, then a negative value is returned. */ @@ -285,17 +338,20 @@ public: Array<Vector3>& contactPoints, Array<Vector3>& contactNormals, const int lastSeparatingAxis = -1); + /** Calculates the depth of penetration between two fixed spheres as well as the deepest point of Sphere A that penetrates Sphere B. The normal returned points <B>away</B> from the object A, although it may represent a perpendicular to either the faces of object B or object A depending on their relative orientations. + @param sphereA Fixed Sphere A. @param sphereB Fixed Sphere B. @param contactPoints Sphere A's deepest point that penetrates Sphere B. [Post Condition] @param contactNormals Normal at penetration point. [Post Condition] + @return Depth of penetration. If there is no intersection between the objects then the depth will be a negative value. */ @@ -304,14 +360,17 @@ public: const Sphere& sphereB, Array<Vector3>& contactPoints, Array<Vector3>& contactNormals = ignoreArray); + /** Calculates the depth of penetration between a fixed sphere and a fixed box as well as the deepest point of the sphere that penetrates the box and the normal at that intersection. + @note There are three possible intersections between a sphere and box. - Sphere completely contained in the box - Sphere intersects one edge - Sphere intersects one vertex + The contact point and contact normal vary for each of these situations. - Sphere contained in Box: - Normal is based on side of least penetration (as is the depth calculation). @@ -322,12 +381,15 @@ public: - Sphere intersects one vertex - Normal is based on vector from the box center to the vertex of penetration. - Point is vertex of penetration. + @cite Adapted from Jim Arvo's method in Graphics Gems See also http://www.win.tue.nl/~gino/solid/gdc2001depth.pdf + @param sphere Fixed Sphere. @param box Fixed Box. @param contactPoints Sphere point that penetrates the box. [Post Condition] @param contactNormals Normal at the penetration point. [Post Condition] + @return Depth of penetration. If there is no intersection between the objects then the depth will be a negative value. */ @@ -336,15 +398,18 @@ public: const Box& box, Array<Vector3>& contactPoints, Array<Vector3>& contactNormals = ignoreArray); + /** Calculates the depth of penetration between a Fixed Sphere and a Fixed Plane as well as the deepest point of the sphere that penetrates the plane and the plane normal at that intersection. + @param sphere Fixed Sphere. @param plane Fixed Plane. @param contactPoints Sphere point that penetrates the plane. [Post Condition] @param contactNormals Normal at penetration point. [Post Condition] + @return Depth of penetration. If there is no intersection between the objects then the depth will be a negative value. */ @@ -353,15 +418,18 @@ public: const class Plane& planeB, Array<Vector3>& contactPoints, Array<Vector3>& contactNormals = ignoreArray); + /** Calculates the depth of penetration between a fixed box and a fixed plane as well as the vertexes of the box that penetrate the plane and the plane normals at those intersections. + @param box Fixed Box. @param plane Fixed Plane. @param contactPoints Box points that penetrate the plane. [Post Condition] @param contactNormals Normals at penetration points [Post Condition] + @return Depth of penetration. If there is no intersection between the objects then the depth will be a negative value. */ @@ -370,18 +438,22 @@ public: const Plane& plane, Array<Vector3>& contactPoints, Array<Vector3>& contactNormals = ignoreArray); + /** Calculates time between the intersection of a moving point and a fixed plane. + @note This is only a one sided collision test. The side defined by the plane's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param point Moving point. @param velocity Point's velocity. @param plane Fixed plane. @param location Location of collision. [Post Condition] (Infinite vector on no collision) @param outNormal Plane's surface normal. [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -391,12 +463,15 @@ public: const class Plane& plane, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving point and a fixed triangle. + @note This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param orig Moving point. @param dir Point's velocity. @param v0 Triangle vertex 1. @@ -404,6 +479,7 @@ public: @param v2 Triangle vertex 3 @param location Location of collision. [Post Condition] (Infinite vector on no collision) + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -415,12 +491,15 @@ public: const Vector3& v2) { return Ray::fromOriginAndDirection(orig, dir).intersectionTime(v0, v1, v2); } + /** Calculates time between the intersection of a moving point and a fixed triangle. + @note This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param orig Moving point. @param dir Point's velocity. @param v0 Triangle vertex 1. @@ -428,6 +507,7 @@ public: @param v2 Triangle vertex 3 @param location Location of collision. [Post Condition] (Infinite vector on no collision) + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -444,18 +524,22 @@ public: } return t; } + /** Calculates time between the intersection of a moving point and a fixed triangle. + @note This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param orig Moving point. @param dir Point's velocity. @param tri Fixed triangle. @param location Location of collision. [Post Condition] (Infinite vector on no collision) @param normal Triangle's surface normal. [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -465,20 +549,25 @@ public: const Triangle& tri, Vector3& location = ignore, Vector3& normal = ignore) { + float t = collisionTimeForMovingPointFixedTriangle( orig, dir, tri.vertex(0), tri.vertex(1), tri.vertex(2)); + if ((t < inf()) && (&location != &ignore)) { location = orig + dir * t; normal = tri.normal(); } return t; } + /** Calculates time between the intersection of a moving point and a fixed triangle. + @note This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param orig Moving point. @param dir Point's velocity. @param v0 Triangle vertex 1. @@ -487,6 +576,7 @@ public: @param location Location of collision. [Post Condition] (Infinite vector on no collision) @param normal Triangle's surface normal. [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -505,11 +595,13 @@ public: } return t; } + /** Unlike other methods, does not support an output normal. If the ray origin is inside the box, returns inf() but inside is set to true. <B>Beta API</B> + @cite Andrew Woo, from "Graphics Gems", Academic Press, 1990 @cite Optimized code by Pierre Terdiman, 2000 (~20-30% faster on my Celeron 500) @cite Epsilon value added by Klaus Hartmann @@ -522,16 +614,20 @@ public: Vector3& outLocation, bool& inside = ignoreBool, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving point and a fixed Axis-Aligned Box (AABox). + @note Avoids the sqrt from collisionTimeForMovingPointFixedAABox. + @param point Moving point. @param velocity Sphere's velocity. @param box Fixed AAbox. @param location Location of collision. [Post Condition] @param Inside Does the ray originate inside the box? [Post Condition] @param normal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -542,16 +638,20 @@ public: Vector3& outLocation, bool& inside = ignoreBool, Vector3& normal = ignore); + /** Calculates time between the intersection of a moving point and a fixed sphere. + @note When ray is starts inside the rectangle, the exiting intersection is detected. + @param point Moving point. @param velocity Point's velocity. @param Sphere Fixed Sphere. @param location Location of collision. [Post Condition] @param outNormal Sphere's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -561,15 +661,19 @@ public: const class Sphere& sphere, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving point and a fixed box. + @note If the point is already inside the box, no collision: inf is returned. + @param point Moving point. @param velocity Sphere's velocity. @param box Fixed box. @param location Position of collision. [Post Condition] @param outNormal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -579,12 +683,15 @@ public: const class Box& box, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving point and a fixed rectangle defined by the points v0, v1, v2, & v3. + @note This is only a one sided collision test. The side defined by the rectangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal. + @param point Moving point. @param velocity Sphere's velocity. @param v0 Rectangle vertex 1. @@ -593,6 +700,7 @@ public: @param v3 Rectangle vertex 4. @param location Location of collision [Post Condition] @param outNormal Rectangle's surface normal. [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -605,14 +713,17 @@ public: const Vector3& v3, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving point and a fixed capsule. + @param point Moving point. @param velocity Point's velocity. @param capsule Fixed capsule. @param location Location of collision. [Post Condition] @param outNormal Capsule's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -622,15 +733,18 @@ public: const class Capsule& capsule, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed triangle. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param plane Fixed Plane. @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -640,15 +754,18 @@ public: const class Plane& plane, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed triangle. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param triangle Fixed Triangle. @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -658,9 +775,11 @@ public: const Triangle& triangle, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed rectangle defined by the points v0, v1, v2, & v3. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param v0 Rectangle vertex 1. @@ -670,6 +789,7 @@ public: @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -682,17 +802,21 @@ public: const Vector3& v3, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed box. + @note This function will not detect an intersection between a moving object that is already interpenetrating the fixed object. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param box Fixed box. @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Box's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -702,17 +826,21 @@ public: const class Box& box, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed sphere. + @note This won't detect a collision if the sphere is already interpenetrating the fixed sphere. + @param movingSphere Moving sphere. @param velocity Sphere's velocity. @param fixedSphere Fixed Sphere. @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Sphere's surface normal to collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -722,17 +850,21 @@ public: const class Sphere& fixedSphere, Vector3& outLocation, Vector3& outNormal = ignore); + /** Calculates time between the intersection of a moving sphere and a fixed capsule. + @note This won't detect a collision if the sphere is already interpenetrating the capsule. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param capsule Fixed capsule. @param location Location of collision -- not center position of sphere at the collision time. [Post Condition] @param outNormal Capsule's surface normal to the collision [Post Condition] + @return Time til collision. If there is no collision then the return value will be inf(). */ @@ -742,16 +874,20 @@ public: const class Capsule& capsule, Vector3& outLocation, Vector3& outNormal = ignore); + /** Finds the direction of bounce that a sphere would have when it intersects an object with the given time of collision, the collision location and the collision normal. + @note This function works like a pong style ball bounce. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param collisionTime Time of collision. @param collisionLocation Collision location. @param collisionNormal Surface collision normal. + @return Direction of bounce. */ static Vector3 bounceDirection( @@ -760,17 +896,21 @@ public: const float collisionTime, const Vector3& collisionLocation, const Vector3& collisionNormal); + /** Finds the direction of slide given a moving sphere, its velocity, the time of collision and the collision location. This function works as if the sphere intersects the surface and continues to hug it. + @note The result will work well for calculating the movement of a player who collides with an object and continues moving along the object instead of just bouncing off it. + @param sphere Moving sphere. @param velocity Sphere's velocity. @param collisionTime Time of collision @param collisionLocation Collision location. + @return Direction of slide. */ static Vector3 slideDirection( @@ -778,27 +918,34 @@ public: const Vector3& velocity, const float collisionTime, const Vector3& collisionLocation); + /** Finds the closest point on a line segment to a given point. + @param v0 line vertex 1. @param v1 line vertex 2. @param point External point. + @return Closests point to <code>point</code> on the line segment. */ static Vector3 closestPointOnLineSegment( const Vector3& v0, const Vector3& v1, const Vector3& point); + /** Finds the closest point on a line segment to a given point. + @note This is an optimization to closestPointOnLineSegment. Edge length and direction can be used in this function if already pre-calculated. This prevents doing the same work twice. + @param v0 line vertex 1. @param v1 line vertex 2. @param edgeDirection The direction of the segment (unit length). @param edgeLength The length of the segment. @param point External point. + @return Closests point to <code>point</code> on the line segment. */ static Vector3 closestPointOnLineSegment( @@ -807,13 +954,16 @@ public: const Vector3& edgeDirection, float edgeLength, const Vector3& point); + /** Finds the closest point on the perimeter of the triangle to an external point; given a triangle defined by three points v0, v1, & v2, and the external point. + @param v0 Triangle vertex 1. @param v1 Triangle vertex 2. @param v2 Triangle vertex 3. @param point External point. + @return Closests point to <code>point</code> on the perimeter of the triangle. */ @@ -822,17 +972,21 @@ public: const Vector3& v1, const Vector3& v2, const Vector3& point); + /** Finds the closest point on the perimeter of the triangle to an external point; given a triangle defined by the array of points v, its edge directions and their lengths, as well as the external point. + @note This is an optimization to closestPointToTrianglePerimeter. Edge length and direction can be used in this function if already pre-calculated. This prevents doing the same work twice. + @param v0 Triangle vertex 1. @param v1 Triangle vertex 2. @param v2 Triangle vertex 3. @param point External point. + @return Closests point to <code>point</code> on the perimeter of the triangle. */ @@ -841,9 +995,11 @@ public: const Vector3 edgeDirection[3], const double edgeLength[3], const Vector3& point); + /** Tests whether a point is contained within the triangle defined by v0, v1, & v2 and its plane's normal. + @param v0 Triangle vertex 1. @param v1 Triangle vertex 2. @param v2 Triangle vertex 3. @@ -851,6 +1007,7 @@ public: @param point The point in question. @param primaryAxis Primary axis of triangle. This will be detected if not given. This parameter is provided as an optimization. + @return true - if point is inside the triangle. @return false - otherwise */ @@ -861,16 +1018,20 @@ public: const Vector3& normal, const Vector3& point, Vector3::Axis primaryAxis = Vector3::DETECT_AXIS); + /** Tests for the intersection of a moving sphere and a fixed box in a given time limit. + @note Returns true if any part of the sphere is inside the box during the time period (inf means "ever"). Useful for performing bounding-box collision detection. + @param sphere Moving sphere. @param velocity Velocity of moving sphere. @param box Fixed box. @param timeLimit Time limit for intersection test. + @return true - if the two objects will touch. @return false - if there is no intersection. */ @@ -879,15 +1040,19 @@ public: const Vector3& velocity, const Box& box, double timeLimit = inf()); + /** Tests for the intersection of a moving sphere and a fixed sphere in a given time limit. + @note This function will not detect an intersection between a moving object that is already interpenetrating the fixed object. + @param sphere Moving sphere. @param velocity Velocity of moving sphere. @param fixedSphere Fixed sphere. @param timeLimit Time limit for intersection test. + @return true - if the two spheres will touch. @return false - if there is no intersection. */ @@ -896,35 +1061,44 @@ public: const Vector3& velocity, const Sphere& fixedSphere, double timeLimit = inf()); + /** Tests for the intersection of two fixed spheres. + @param sphere1 Fixed sphere 1. @param sphere2 Fixed sphere 2. + @return true - if the two spheres touch. @return false - if there is no intersection. */ static bool fixedSolidSphereIntersectsFixedSolidSphere( const Sphere& sphere1, const Sphere& sphere2); + /** Tests for the intersection of a fixed sphere and a fixed box. + @param sphere Fixed sphere. @param box Fixed box. + @return true - if the two objects touch. @return false - if there is no intersection. */ static bool fixedSolidSphereIntersectsFixedSolidBox( const Sphere& sphere, const Box& box); + /** Tests whether a point is inside a rectangle defined by the vertexes v0, v1, v2, & v3, and the rectangle's plane normal. + @param v0 Rectangle vertex 1. @param v1 Rectangle vertex 2. @param v2 Rectangle vertex 3. @param v3 Rectangle vertex 4. @param normal Normal to rectangle's plane. @param point The point in question. + @return true - if point is inside the rectangle. @return false - otherwise */ @@ -935,15 +1109,18 @@ public: const Vector3& v3, const Vector3& normal, const Vector3& point); + /** Finds the closest point on the perimeter of the rectangle to an external point; given a rectangle defined by four points v0, v1, v2, & v3, and the external point. + @param v0 Rectangle vertex 1. @param v1 Rectangle vertex 2. @param v2 Rectangle vertex 3. @param v3 Rectangle vertex 4. @param point External point. + @return Closests point to <code>point</code> on the perimeter of the rectangle. */ @@ -953,15 +1130,18 @@ public: const Vector3& v2, const Vector3& v3, const Vector3& point); + /** Finds the closest point in the rectangle to an external point; Given a rectangle defined by four points v0, v1, v2, & v3, and the external point. + @param v0 Rectangle vertex 1. @param v1 Rectangle vertex 2. @param v2 Rectangle vertex 3 @param v3 Rectangle vertex 4. @param point External point. + @return Closet point in the rectangle to the external point. */ static Vector3 closestPointToRectangle( @@ -971,6 +1151,8 @@ public: const Vector3& v3, const Vector3& point); }; + } // namespace + #endif // G3D_COLLISIONDETECTION_H diff --git a/dep/include/g3dlite/G3D/CoordinateFrame.h b/dep/include/g3dlite/G3D/CoordinateFrame.h index 9f7bb609dc9..62cbbd47639 100644 --- a/dep/include/g3dlite/G3D/CoordinateFrame.h +++ b/dep/include/g3dlite/G3D/CoordinateFrame.h @@ -1,13 +1,18 @@ /** @file CoordinateFrame.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-03-04 @edited 2006-04-07 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_COORDINATEFRAME_H #define G3D_COORDINATEFRAME_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Vector4.h" @@ -18,63 +23,85 @@ #include <stdio.h> #include <cstdarg> #include <assert.h> + namespace G3D { + /** A rigid body RT (rotation-translation) transformation. + CoordinateFrame abstracts a 4x4 matrix that maps object space to world space: + v_world = C * v_object + CoordinateFrame::rotation is the upper 3x3 submatrix, CoordinateFrame::translation is the right 3x1 column. The 4th row is always [0 0 0 1], so it isn't stored. So you don't have to remember which way the multiplication and transformation work, it provides explicit toWorldSpace and toObjectSpace methods. Also, points, vectors (directions), and surface normals transform differently, so they have separate methods. + Some helper functions transform whole primitives like boxes in and out of object space. + Convert to Matrix4 using CoordinateFrame::toMatrix4. You <I>can</I> construct a CoordinateFrame from a Matrix4 using Matrix4::approxCoordinateFrame, however, because a Matrix4 is more general than a CoordinateFrame, some information may be lost. + See also: G3D::Matrix4, G3D::Quat */ class CoordinateFrame { public: + /** Takes object space points to world space. */ Matrix3 rotation; + /** Takes object space points to world space. */ Vector3 translation; + /** The direction an object "looks" relative to its own axes. @deprecated This is always -1 and will be fixed at that value in future releases. */ static const float zLookDirection; + inline bool operator==(const CoordinateFrame& other) const { return (translation == other.translation) && (rotation == other.rotation); } + inline bool operator!=(const CoordinateFrame& other) const { return !(*this == other); } + bool fuzzyEq(const CoordinateFrame& other) const; + bool fuzzyIsIdentity() const; + bool isIdentity() const; + /** Initializes to the identity coordinate frame. */ inline CoordinateFrame() : rotation(Matrix3::identity()), translation(Vector3::zero()) { } + CoordinateFrame(const Vector3& _translation) : rotation(Matrix3::identity()), translation(_translation) { } + CoordinateFrame(const Matrix3 &rotation, const Vector3 &translation) : rotation(rotation), translation(translation) { } + CoordinateFrame(const Matrix3 &rotation) : rotation(rotation), translation(Vector3::zero()) { } + CoordinateFrame(const CoordinateFrame &other) : rotation(other.rotation), translation(other.translation) {} + /** Computes the inverse of this coordinate frame. */ @@ -84,17 +111,22 @@ public: out.translation = -out.rotation * translation; return out; } + inline ~CoordinateFrame() {} + /** See also Matrix4::approxCoordinateFrame */ class Matrix4 toMatrix4() const; + /** Produces an XML serialization of this coordinate frame. */ std::string toXML() const; + /** Returns the heading of the lookVector as an angle in radians relative to the world -z axis. That is, a counter-clockwise heading where north (-z) is 0 and west (-x) is PI/2. + Note that the heading ignores the Y axis, so an inverted object has an inverted heading. */ @@ -103,6 +135,7 @@ public: float angle = -(float) atan2(-look.x, look.z); return angle; } + /** Takes the coordinate frame into object space. this->inverse() * c @@ -110,12 +143,15 @@ public: inline CoordinateFrame toObjectSpace(const CoordinateFrame& c) const { return this->inverse() * c; } + inline Vector4 toObjectSpace(const Vector4& v) const { return this->inverse().toWorldSpace(v); } + inline Vector4 toWorldSpace(const Vector4& v) const { return Vector4(rotation * Vector3(v.x, v.y, v.z) + translation * v.w, v.w); } + /** Transforms the point into world space. */ @@ -125,6 +161,7 @@ public: rotation[1][0] * v[0] + rotation[1][1] * v[1] + rotation[1][2] * v[2] + translation[1], rotation[2][0] * v[0] + rotation[2][1] * v[1] + rotation[2][2] * v[2] + translation[2]); } + /** Transforms the point into object space. */ @@ -138,17 +175,22 @@ public: rotation[0][1] * p[0] + rotation[1][1] * p[1] + rotation[2][1] * p[2], rotation[0][2] * p[0] + rotation[1][2] * p[1] + rotation[2][2] * p[2]); } + /** Transforms the vector into world space (no translation). */ inline Vector3 vectorToWorldSpace(const Vector3& v) const { return rotation * v; } + inline Vector3 normalToWorldSpace(const Vector3& v) const { return rotation * v; } + class Ray toObjectSpace(const Ray& r) const; + Ray toWorldSpace(const Ray& r) const; + /** Transforms the vector into object space (no translation). */ @@ -156,57 +198,86 @@ public: // Multiply on the left (same as rotation.transpose() * v) return v * rotation; } + inline Vector3 normalToObjectSpace(const Vector3 &v) const { // Multiply on the left (same as rotation.transpose() * v) return v * rotation; } + void pointToWorldSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + void normalToWorldSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + void vectorToWorldSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + void pointToObjectSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + void normalToObjectSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + void vectorToObjectSpace(const Array<Vector3>& v, Array<Vector3>& vout) const; + class Box toWorldSpace(const class AABox& b) const; + class Box toWorldSpace(const class Box& b) const; + class Cylinder toWorldSpace(const class Cylinder& b) const; + class Capsule toWorldSpace(const class Capsule& b) const; + class Plane toWorldSpace(const class Plane& p) const; + class Sphere toWorldSpace(const class Sphere& b) const; + class Triangle toWorldSpace(const class Triangle& t) const; + class Box toObjectSpace(const AABox& b) const; + class Box toObjectSpace(const Box& b) const; + class Plane toObjectSpace(const Plane& p) const; + class Sphere toObjectSpace(const Sphere& b) const; + Triangle toObjectSpace(const Triangle& t) const; + /** Compose: create the transformation that is <I>other</I> followed by <I>this</I>.*/ CoordinateFrame operator*(const CoordinateFrame &other) const { return CoordinateFrame(rotation * other.rotation, pointToWorldSpace(other.translation)); } + CoordinateFrame operator+(const Vector3& v) const { return CoordinateFrame(rotation, translation + v); } + CoordinateFrame operator-(const Vector3& v) const { return CoordinateFrame(rotation, translation - v); } + void lookAt(const Vector3& target); + void lookAt( const Vector3& target, Vector3 up); + /** @deprecated See lookVector */ inline Vector3 getLookVector() const { return rotation.getColumn(2) * zLookDirection; } + /** The direction this camera is looking (its negative z axis)*/ inline Vector3 lookVector() const { return rotation.getColumn(2) * zLookDirection; } + /** Returns the ray starting at the camera origin travelling in direction CoordinateFrame::lookVector. */ class Ray lookRay() const; + /** Up direction for this camera (its y axis). */ inline Vector3 upVector() const { return rotation.getColumn(1); } + /** If a viewer looks along the look vector, this is the viewer's "left" @deprecated leftVector @@ -214,10 +285,12 @@ public: inline Vector3 getLeftVector() const { return -rotation.getColumn(0); } + /** @deprecated See rightVector */ inline Vector3 getRightVector() const { return rotation.getColumn(0); } + /** If a viewer looks along the look vector, this is the viewer's "left". Useful for strafing motions and building alternative coordinate frames. @@ -225,9 +298,11 @@ public: inline Vector3 leftVector() const { return -rotation.getColumn(0); } + inline Vector3 rightVector() const { return rotation.getColumn(0); } + /** Linearly interpolates between two coordinate frames, using Quat::slerp for the rotations. @@ -235,7 +310,10 @@ public: CoordinateFrame lerp( const CoordinateFrame& other, float alpha) const; + }; + } // namespace + #endif diff --git a/dep/include/g3dlite/G3D/Crypto.h b/dep/include/g3dlite/G3D/Crypto.h index 73eaeeb8fa4..2805e8590c2 100644 --- a/dep/include/g3dlite/G3D/Crypto.h +++ b/dep/include/g3dlite/G3D/Crypto.h @@ -1,34 +1,47 @@ /** @file Crypto.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2006-03-29 @edited 2006-04-06 */ + #ifndef G3D_CRYPTO_H #define G3D_CRYPTO_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include <string> + namespace G3D { + /** Cryptography and hashing helper functions */ class Crypto { public: + /** Computes the CRC32 value of a byte array. CRC32 is designed to be a hash function that produces different values for similar strings. + This implementation is compatible with PKZIP and GZIP. + Based on http://www.gamedev.net/reference/programming/features/crc32/ */ static uint32 crc32(const void* bytes, size_t numBytes); + /** Returns the nth prime less than 2000 in constant time. The first prime has index 0 and is the number 2. */ static int smallPrime(int n); + /** Returns 1 + the largest value that can be passed to smallPrime. */ static int numSmallPrimes(); }; + } + #endif diff --git a/dep/include/g3dlite/G3D/GCamera.h b/dep/include/g3dlite/G3D/GCamera.h index c7e2f5aa711..50d5ca2244e 100644 --- a/dep/include/g3dlite/G3D/GCamera.h +++ b/dep/include/g3dlite/G3D/GCamera.h @@ -1,57 +1,74 @@ /** @file GCamera.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2006-02-11 */ + #ifndef G3D_GCAMERA_H #define G3D_GCAMERA_H + #include "G3D/platform.h" #include "G3D/CoordinateFrame.h" #include "G3D/Vector3.h" #include "G3D/Plane.h" + namespace G3D { + /** There is a viewport of width x height size in world space that corresponds to a screenWidth x screenHeight pixel grid on a renderDevice->getWidth() x renderDevice->getHeight() window. + All viewport arguments are the pixel bounds of the viewport-- e.g., RenderDevice::getViewport(). */ class GCamera { private: + /** Vertical field of view (in radians) */ float fieldOfView; + /** The image plane depth corresponding to a vertical field of view, where the film size is 1x1. */ float imagePlaneDepth; + /** Clipping plane, *not* imaging plane. Positive numbers. */ float nearPlane; + /** Positive */ float farPlane; + CoordinateFrame cframe; + public: + class Frustum { public: class Face { public: /** Counter clockwise indices into vertexPos */ int vertexIndex[4]; + /** The plane containing the face. */ Plane plane; }; + /** The vertices, in homogeneous space. If w == 0, a vertex is at infinity. */ Array<Vector4> vertexPos; + /** The faces in the frustum. When the far plane is at infinity, there are 5 faces, otherwise there are 6. The faces are in the order @@ -59,12 +76,16 @@ public: */ Array<Face> faceArray; }; + GCamera(); + virtual ~GCamera(); + CoordinateFrame getCoordinateFrame() const; void getCoordinateFrame(CoordinateFrame& c) const; void setCoordinateFrame(const CoordinateFrame& c); + /** Sets the horizontal field of view, in radians. The initial angle is toRadians(55). @@ -75,6 +96,7 @@ public: </UL> */ void setFieldOfView(float angle); + /** Sets the field of view based on a desired image plane depth (<I>s'</I>) and film dimensions in world space. Depth must be positive. Width, @@ -87,23 +109,28 @@ public: void setImagePlaneDepth( float depth, const class Rect2D& viewport); + inline double getFieldOfView() const { return fieldOfView; } + /** Projects a world space point onto a width x height screen. The returned coordinate uses pixmap addressing: x = right and y = down. The resulting z value is <I>rhw</I>. + If the point is behind the camera, Vector3::inf() is returned. */ G3D::Vector3 project( const G3D::Vector3& point, const class Rect2D& viewport) const; + /** Returns the pixel area covered by a shape of the given world space area at the given z value (z must be negative). */ float worldToScreenSpaceArea(float area, float z, const class Rect2D& viewport) const; + /** Returns the world space 3D viewport corners. These are at the near clipping plane. The corners are constructed @@ -116,6 +143,7 @@ public: Vector3& outUL, Vector3& outLL, Vector3& outLR) const; + /** Returns the image plane depth, <I>s'</I>, given the current field of view for film of dimensions width x height. See @@ -124,12 +152,14 @@ public: float getImagePlaneDepth( const class Rect2D& viewport) const; + /** Returns the world space ray passing through the center of pixel (x, y) on the image plane. The pixel x and y axes are opposite the 3D object space axes: (0,0) is the upper left corner of the screen. They are in viewport coordinates, not screen coordinates. + Integer (x, y) values correspond to the upper left corners of pixels. If you want to cast rays through pixel centers, add 0.5 to x and y. @@ -139,36 +169,43 @@ public: float y, const class Rect2D& viewport) const; + /** Returns a negative z-value. */ inline float getNearPlaneZ() const { return -nearPlane; } + /** Returns a negative z-value. */ inline float getFarPlaneZ() const { return -farPlane; } + inline void setFarPlaneZ(float z) { debugAssert(z < 0); farPlane = -z; } + inline void setNearPlaneZ(float z) { debugAssert(z < 0); nearPlane = -z; } + /** Returns the GCamera space width of the viewport. */ float getViewportWidth( const class Rect2D& viewport) const; + /** Returns the GCamera space height of the viewport. */ float getViewportHeight( const class Rect2D& viewport) const; + /** Read back a GCamera space z-value at pixel (x, y) from the depth buffer. double getZValue( @@ -177,28 +214,39 @@ public: const class Rect2D& viewport, double polygonOffset = 0) const; */ + void setPosition(const Vector3& t); + void lookAt(const Vector3& position, const Vector3& up = Vector3::unitY()); + /** Returns the clipping planes of the frustum, in world space. The planes have normals facing <B>into</B> the view frustum. + The plane order is guaranteed to be: Near, Right, Left, Top, Bottom, [Far] + If the far plane is at infinity, the resulting array will have 5 planes, otherwise there will be 6. + The viewport is used only to determine the aspect ratio of the screen; the absolute dimensions and xy values don't matter. */ void getClipPlanes( const Rect2D& viewport, Array<Plane>& outClip) const; + /** Returns the world space view frustum, which is a truncated pyramid describing the volume of space seen by this camera. */ void getFrustum(const Rect2D& viewport, GCamera::Frustum& f) const; + GCamera::Frustum frustum(const Rect2D& viewport) const; + }; + } // namespace G3D + #endif diff --git a/dep/include/g3dlite/G3D/Line.h b/dep/include/g3dlite/G3D/Line.h index 0741e2f804f..724d5ef88cb 100644 --- a/dep/include/g3dlite/G3D/Line.h +++ b/dep/include/g3dlite/G3D/Line.h @@ -1,64 +1,86 @@ /** @file Line.h + Line class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2006-02-28 */ + #ifndef G3D_LINE_H #define G3D_LINE_H + #include "G3D/platform.h" #include "G3D/Vector3.h" + namespace G3D { + class Plane; + /** An infinite 3D line. */ class Line { protected: + Vector3 _point; Vector3 _direction; + Line(const Vector3& point, const Vector3& direction) { _point = point; _direction = direction.direction(); } + public: + /** Undefined (provided for creating Array<Line> only) */ inline Line() {} + virtual ~Line() {} + /** Constructs a line from two (not equal) points. */ static Line fromTwoPoints(const Vector3 &point1, const Vector3 &point2) { return Line(point1, point2 - point1); } + /** Creates a line from a point and a (nonzero) direction. */ static Line fromPointAndDirection(const Vector3& point, const Vector3& direction) { return Line(point, direction); } + /** Returns the closest point on the line to point. */ Vector3 closestPoint(const Vector3& pt) const; + /** Returns the distance between point and the line */ double distance(const Vector3& point) const { return (closestPoint(point) - point).magnitude(); } + /** Returns a point on the line */ Vector3 point() const; + /** Returns the direction (or negative direction) of the line */ Vector3 direction() const; + /** Returns the point where the line and plane intersect. If there is no intersection, returns a point at infinity. */ Vector3 intersection(const Plane &plane) const; }; + };// namespace + #endif diff --git a/dep/include/g3dlite/G3D/Matrix3.h b/dep/include/g3dlite/G3D/Matrix3.h index 3c7849a4121..0fd85b306c9 100644 --- a/dep/include/g3dlite/G3D/Matrix3.h +++ b/dep/include/g3dlite/G3D/Matrix3.h @@ -1,50 +1,67 @@ /** @file Matrix3.h + 3x3 matrix class + @maintainer Morgan McGuire, matrix@graphics3d.com + @cite Portions based on Dave Eberly's Magic Software Library at <A HREF="http://www.magic-software.com">http://www.magic-software.com</A> + @created 2001-06-02 @edited 2006-04-05 */ + #ifndef G3D_MATRIX3_H #define G3D_MATRIX3_H + #include "G3D/platform.h" #include "G3D/System.h" #include "G3D/Vector3.h" #include "G3D/Vector4.h" + namespace G3D { + /** 3x3 matrix. Do not subclass. */ class Matrix3 { private: + float elt[3][3]; + // Hidden operators bool operator<(const Matrix3&) const; bool operator>(const Matrix3&) const; bool operator<=(const Matrix3&) const; bool operator>=(const Matrix3&) const; + public: + /** Initial values are undefined for performance. See also Matrix3::zero(), Matrix3::identity(), Matrix3::fromAxisAngle, etc.*/ inline Matrix3() {} + Matrix3 (const float aafEntry[3][3]); Matrix3 (const Matrix3& rkMatrix); Matrix3 (float fEntry00, float fEntry01, float fEntry02, float fEntry10, float fEntry11, float fEntry12, float fEntry20, float fEntry21, float fEntry22); + bool fuzzyEq(const Matrix3& b) const; + /** Constructs a matrix from a quaternion. @cite Graphics Gems II, p. 351--354 @cite Implementation from Watt and Watt, pg 362*/ Matrix3(const class Quat& q); + /** Sets all elements. */ void set(float fEntry00, float fEntry01, float fEntry02, float fEntry10, float fEntry11, float fEntry12, float fEntry20, float fEntry21, float fEntry22); + /** * member access, allows use of construct mat[r][c] */ @@ -53,68 +70,84 @@ public: debugAssert(iRow < 3); return (float*)&elt[iRow][0]; } + inline const float* operator[] (int iRow) const { debugAssert(iRow >= 0); debugAssert(iRow < 3); return (const float*)&elt[iRow][0]; } + inline operator float* () { return (float*)&elt[0][0]; } + inline operator const float* () const{ return (const float*)&elt[0][0]; } + Vector3 getColumn (int iCol) const; Vector3 getRow (int iRow) const; void setColumn(int iCol, const Vector3 &vector); void setRow(int iRow, const Vector3 &vector); + // assignment and comparison inline Matrix3& operator= (const Matrix3& rkMatrix) { System::memcpy(elt, rkMatrix.elt, 9 * sizeof(float)); return *this; } + bool operator== (const Matrix3& rkMatrix) const; bool operator!= (const Matrix3& rkMatrix) const; + // arithmetic operations Matrix3 operator+ (const Matrix3& rkMatrix) const; Matrix3 operator- (const Matrix3& rkMatrix) const; /** Matrix-matrix multiply */ Matrix3 operator* (const Matrix3& rkMatrix) const; Matrix3 operator- () const; + Matrix3& operator+= (const Matrix3& rkMatrix); Matrix3& operator-= (const Matrix3& rkMatrix); Matrix3& operator*= (const Matrix3& rkMatrix); + /** * matrix * vector [3x3 * 3x1 = 3x1] */ inline Vector3 operator* (const Vector3& v) const { Vector3 kProd; + for (int r = 0; r < 3; ++r) { kProd[r] = elt[r][0] * v[0] + elt[r][1] * v[1] + elt[r][2] * v[2]; } + return kProd; } + /** * vector * matrix [1x3 * 3x3 = 1x3] */ friend Vector3 operator* (const Vector3& rkVector, const Matrix3& rkMatrix); + /** * matrix * scalar */ Matrix3 operator* (float fScalar) const; + /** scalar * matrix */ friend Matrix3 operator* (double fScalar, const Matrix3& rkMatrix); friend Matrix3 operator* (float fScalar, const Matrix3& rkMatrix); friend Matrix3 operator* (int fScalar, const Matrix3& rkMatrix); + private: /** Multiplication where out != A and out != B */ static void _mul(const Matrix3& A, const Matrix3& B, Matrix3& out); public: + /** Optimized implementation of out = A * B. It is safe (but slow) to call with A, B, and out possibly pointer equal to one another.*/ // This is a static method so that it is not ambiguous whether "this" @@ -128,11 +161,14 @@ public: _mul(A, B, out); } } + private: static void _transpose(const Matrix3& A, Matrix3& out); public: + /** Optimized implementation of out = A.transpose(). It is safe (but slow) to call with A and out possibly pointer equal to one another. + Note that <CODE>A.transpose() * v</CODE> can be computed more efficiently as <CODE>v * A</CODE>. */ @@ -143,27 +179,36 @@ public: _transpose(A, out); } } + /** Returns true if the rows and column L2 norms are 1.0 and the rows are orthogonal. */ bool isOrthonormal() const; + Matrix3 transpose () const; bool inverse (Matrix3& rkInverse, float fTolerance = 1e-06) const; Matrix3 inverse (float fTolerance = 1e-06) const; float determinant () const; + /** singular value decomposition */ void singularValueDecomposition (Matrix3& rkL, Vector3& rkS, Matrix3& rkR) const; /** singular value decomposition */ void singularValueComposition (const Matrix3& rkL, const Vector3& rkS, const Matrix3& rkR); + /** Gram-Schmidt orthonormalization (applied to columns of rotation matrix) */ void orthonormalize(); + /** orthogonal Q, diagonal D, upper triangular U stored as (u01,u02,u12) */ void qDUDecomposition (Matrix3& rkQ, Vector3& rkD, Vector3& rkU) const; + float spectralNorm () const; + /** matrix must be orthonormal */ void toAxisAngle(Vector3& rkAxis, float& rfRadians) const; + static Matrix3 fromAxisAngle(const Vector3& rkAxis, float fRadians); + /** * The matrix must be orthonormal. The decomposition is yaw*pitch*roll * where yaw is rotation about the Up vector, pitch is rotation about the @@ -187,13 +232,17 @@ public: static Matrix3 fromEulerAnglesYZX (float fYAngle, float fPAngle, float fRAngle); static Matrix3 fromEulerAnglesZXY (float fYAngle, float fPAngle, float fRAngle); static Matrix3 fromEulerAnglesZYX (float fYAngle, float fPAngle, float fRAngle); + /** eigensolver, matrix must be symmetric */ void eigenSolveSymmetric (float afEigenvalue[3], Vector3 akEigenvector[3]) const; + static void tensorProduct (const Vector3& rkU, const Vector3& rkV, Matrix3& rkProduct); std::string toString() const; + static const float EPSILON; + // Special values. // The unguaranteed order of initialization of static variables across // translation units can be a source of annoying bugs, so now the static @@ -214,15 +263,18 @@ public: // http://www.mindview.net/ static const Matrix3& zero(); static const Matrix3& identity(); + // Deprecated. /** @deprecated Use Matrix3::zero() */ static const Matrix3 ZERO; /** @deprecated Use Matrix3::identity() */ static const Matrix3 IDENTITY; + protected: // support for eigensolver void tridiagonal (float afDiag[3], float afSubDiag[3]); bool qLAlgorithm (float afDiag[3], float afSubDiag[3]); + // support for singular value decomposition static const float ms_fSvdEpsilon; static const int ms_iSvdMaxIterations; @@ -230,23 +282,31 @@ protected: Matrix3& kR); static void golubKahanStep (Matrix3& kA, Matrix3& kL, Matrix3& kR); + // support for spectral norm static float maxCubicRoot (float afCoeff[3]); + }; + //---------------------------------------------------------------------------- /** <code>v * M == M.transpose() * v</code> */ inline Vector3 operator* (const Vector3& rkPoint, const Matrix3& rkMatrix) { Vector3 kProd; + for (int r = 0; r < 3; ++r) { kProd[r] = rkPoint[0] * rkMatrix.elt[0][r] + rkPoint[1] * rkMatrix.elt[1][r] + rkPoint[2] * rkMatrix.elt[2][r]; } + return kProd; } + } // namespace + #endif + diff --git a/dep/include/g3dlite/G3D/Plane.h b/dep/include/g3dlite/G3D/Plane.h index 3d57ad1bec8..c7043e23c42 100644 --- a/dep/include/g3dlite/G3D/Plane.h +++ b/dep/include/g3dlite/G3D/Plane.h @@ -1,32 +1,44 @@ /** @file Plane.h + Plane class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2004-07-18 */ + #ifndef G3D_PLANE_H #define G3D_PLANE_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Vector4.h" + namespace G3D { + /** An infinite 2D plane in 3D space. */ class Plane { private: + /** normal.Dot(x,y,z) = distance */ Vector3 _normal; float _distance; + /** Assumes the normal has unit length. */ Plane(const Vector3& n, float d) : _normal(n), _distance(d) { } + public: + Plane() : _normal(Vector3::unitY()), _distance(0) { } + /** Constructs a plane from three points. */ @@ -34,6 +46,7 @@ public: const Vector3& point0, const Vector3& point1, const Vector3& point2); + /** Constructs a plane from three points, where at most two are at infinity (w = 0, not xyz = inf). @@ -42,14 +55,18 @@ public: Vector4 point0, Vector4 point1, Vector4 point2); + /** The normal will be unitized. */ Plane( const Vector3& __normal, const Vector3& point); + static Plane fromEquation(float a, float b, float c, float d); + virtual ~Plane() {} + /** Returns true if point is on the side the normal points to or is in the plane. @@ -57,10 +74,12 @@ public: inline bool halfSpaceContains(Vector3 point) const { // Clamp to a finite range for testing point = point.clamp(Vector3::minFinite(), Vector3::maxFinite()); + // We can get away with putting values *at* the limits of the float32 range into // a dot product, since the dot product is carried out on float64. return _normal.dot(point) >= _distance; } + /** Returns true if point is on the side the normal points to or is in the plane. @@ -72,6 +91,7 @@ public: return halfSpaceContains(point.xyz() / point.w); } } + /** Returns true if point is on the side the normal points to or is in the plane. Only call on finite points. Faster than halfSpaceContains. @@ -80,46 +100,58 @@ public: debugAssert(point.isFinite()); return _normal.dot(point) >= _distance; } + /** Returns true if the point is nearly in the plane. */ inline bool fuzzyContains(const Vector3 &point) const { return fuzzyEq(point.dot(_normal), _distance); } + inline const Vector3& normal() const { return _normal; } + /** Returns distance from point to plane. Distance is negative if point is behind (not in plane in direction opposite normal) the plane. */ inline float distance(const Vector3& x) const { return (_normal.dot(x) - _distance); } + inline Vector3 closestPoint(const Vector3& x) const { return x + (_normal * (-distance(x))); } + /** Returns normal * distance from origin */ Vector3 center() const { return _normal * _distance; } + /** Inverts the facing direction of the plane so the new normal is the inverse of the old normal. */ void flip(); + /** Returns the equation in the form: + <CODE>normal.Dot(Vector3(<I>x</I>, <I>y</I>, <I>z</I>)) + d = 0</CODE> */ void getEquation(Vector3 &normal, double& d) const; void getEquation(Vector3 &normal, float& d) const; + /** ax + by + cz + d = 0 */ void getEquation(double& a, double& b, double& c, double& d) const; void getEquation(float& a, float& b, float& c, float& d) const; + std::string toString() const; }; + } // namespace + #endif diff --git a/dep/include/g3dlite/G3D/Quat.h b/dep/include/g3dlite/G3D/Quat.h index 2c7fe68353e..f53d70be909 100644 --- a/dep/include/g3dlite/G3D/Quat.h +++ b/dep/include/g3dlite/G3D/Quat.h @@ -1,34 +1,46 @@ /** @file Quat.h + Quaternion + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2002-01-23 @edited 2006-05-10 */ + #ifndef G3D_QUAT_H #define G3D_QUAT_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include "G3D/Vector3.h" #include "G3D/Matrix3.h" #include <string> + namespace G3D { + /** Unit quaternions are used in computer graphics to represent rotation about an axis. Any 3x3 rotation matrix can be stored as a quaternion. + A quaternion represents the sum of a real scalar and an imaginary vector: ix + jy + kz + w. A unit quaternion representing a rotation by A about axis v has the form [sin(A/2)*v, cos(A/2)]. For a unit quaternion, q.conj() == q.inverse() is a rotation by -A about v. -q is the same rotation as q (negate both the axis and angle). + A non-unit quaterion q represents the same rotation as q.unitize() (Dam98 pg 28). + Although quaternion-vector operations (eg. Quat + Vector3) are well defined, they are not supported by this class because they typically are bugs when they appear in code. + Do not subclass. + <B>BETA API -- subject to change</B> @cite Erik B. Dam, Martin Koch, Martin Lillholm, Quaternions, Interpolation and Animation. Technical Report DIKU-TR-98/5, Department of Computer Science, University of Copenhagen, Denmark. 1998. */ @@ -39,64 +51,81 @@ private: bool operator>(const Quat&) const; bool operator<=(const Quat&) const; bool operator>=(const Quat&) const; + public: + /** q = [sin(angle / 2) * axis, cos(angle / 2)] + In Watt & Watt's notation, s = w, v = (x, y, z) In the Real-Time Rendering notation, u = (x, y, z), w = w */ float x, y, z, w; + /** Initializes to a zero degree rotation. */ inline Quat() : x(0), y(0), z(0), w(1) {} + Quat( const Matrix3& rot); + inline Quat(float _x, float _y, float _z, float _w) : x(_x), y(_y), z(_z), w(_w) {} + /** Defaults to a pure vector quaternion */ inline Quat(const Vector3& v, float _w = 0) : x(v.x), y(v.y), z(v.z), w(_w) { } + /** The real part of the quaternion. */ inline const float& real() const { return w; } + inline float& real() { return w; } + /** Note: two quats can represent the Quat::sameRotation and not be equal. */ bool fuzzyEq(const Quat& q) { return G3D::fuzzyEq(x, q.x) && G3D::fuzzyEq(y, q.y) && G3D::fuzzyEq(z, q.z) && G3D::fuzzyEq(w, q.w); } + /** True if these quaternions represent the same rotation (note that every rotation is represented by two values; q and -q). */ bool sameRotation(const Quat& q) { return fuzzyEq(q) || fuzzyEq(-q); } + inline Quat operator-() const { return Quat(-x, -y, -z, -w); } + /** Returns the imaginary part (x, y, z) */ inline const Vector3& imag() const { return *(reinterpret_cast<const Vector3*>(this)); } + inline Vector3& imag() { return *(reinterpret_cast<Vector3*>(this)); } + /** q = [sin(angle/2)*axis, cos(angle/2)] */ static Quat fromAxisAngleRotation( const Vector3& axis, float angle); + /** Returns the axis and angle of rotation represented by this quaternion (i.e. q = [sin(angle/2)*axis, cos(angle/2)]) */ void toAxisAngleRotation( Vector3& axis, double& angle) const; + void toAxisAngleRotation( Vector3& axis, float& angle) const { @@ -104,13 +133,18 @@ public: toAxisAngleRotation(axis, d); angle = (float)d; } + Matrix3 toRotationMatrix() const; + void toRotationMatrix( Matrix3& rot) const; + /** Spherical linear interpolation: linear interpolation along the shortest (3D) great-circle route between two quaternions. + Note: Correct rotations are expected between 0 and PI in the right order. + @cite Based on Game Physics -- David Eberly pg 538-540 @param threshold Critical angle between between rotations at which the algorithm switches to normalized lerp, which is more @@ -120,56 +154,72 @@ public: const Quat& other, float alpha, float threshold = 0.05f) const; + /** Normalized linear interpolation of quaternion components. */ Quat nlerp(const Quat& other, float alpha) const; + /** Negates the imaginary part. */ inline Quat conj() const { return Quat(-x, -y, -z, w); } + inline float sum() const { return x + y + z + w; } + inline float average() const { return sum() / 4.0f; } + inline Quat operator*(float s) const { return Quat(x * s, y * s, z * s, w * s); } + /** @cite Based on Watt & Watt, page 360 */ friend Quat operator* (float s, const Quat& q); + inline Quat operator/(float s) const { return Quat(x / s, y / s, z / s, w / s); } + inline float dot(const Quat& other) const { return (x * other.x) + (y * other.y) + (z * other.z) + (w * other.w); } + /** Note that q<SUP>-1</SUP> = q.conj() for a unit quaternion. @cite Dam99 page 13 */ inline Quat inverse() const { return conj() / dot(*this); } + Quat operator-(const Quat& other) const; + Quat operator+(const Quat& other) const; + /** Quaternion multiplication (composition of rotations). Note that this does not commute. */ Quat operator*(const Quat& other) const; + /* (*this) * other.inverse() */ Quat operator/(const Quat& other) const { return (*this) * other.inverse(); } + /** Is the magnitude nearly 1.0? */ inline bool isUnit(float tolerance = 1e-5) const { return abs(dot(*this) - 1.0f) < tolerance; } + inline float magnitude() const { return sqrtf(dot(*this)); } + inline Quat log() const { if ((x == 0) && (y == 0) && (z == 0)) { if (w > 0) { @@ -197,14 +247,17 @@ public: // Solve for A in q = [sin(A)*v, cos(A)] Vector3 u(x, y, z); double len = u.magnitude(); + if (len == 0.0) { return } double A = atan2((double)w, len); Vector3 v = u / len; + return Quat(v * A, 0); } */ + /** exp q = [sin(A) * v, cos(A)] where q = [Av, 0]. Only defined for pure-vector quaternions */ inline Quat exp() const { @@ -215,10 +268,12 @@ public: return Quat(sinf(A) * v, cosf(A)); } + /** Raise this quaternion to a power. For a rotation, this is the effect of rotating x times as much as the original quaterion. + Note that q.pow(a).pow(b) == q.pow(a + b) @cite Dam98 pg 21 */ @@ -226,6 +281,7 @@ public: return (log() * x).exp(); } + /** @deprecated Use toUnit() @@ -238,6 +294,7 @@ public: return *this / sqrtf(mag2); } } + /** Returns a unit quaterion obtained by dividing through by the magnitude. @@ -245,6 +302,7 @@ public: inline Quat toUnit() const { return unitize(); } + /** The linear algebra 2-norm, sqrt(q dot q). This matches the value used in Dam's 1998 tech report but differs from the @@ -254,6 +312,7 @@ public: inline float norm() const { return magnitude(); } + // access quaternion as q[0] = q.x, q[1] = q.y, q[2] = q.z, q[3] = q.w // // WARNING. These member functions rely on @@ -261,11 +320,14 @@ public: // (2) the data packed in a 4*sizeof(float) memory block const float& operator[] (int i) const; float& operator[] (int i); + /** Generate uniform random unit quaternion (i.e. random "direction") @cite From "Uniform Random Rotations", Ken Shoemake, Graphics Gems III. */ static Quat unitRandom(); + // 2-char swizzles + Vector2 xx() const; Vector2 yx() const; Vector2 zx() const; @@ -282,7 +344,9 @@ public: Vector2 yw() const; Vector2 zw() const; Vector2 ww() const; + // 3-char swizzles + Vector3 xxx() const; Vector3 yxx() const; Vector3 zxx() const; @@ -347,7 +411,9 @@ public: Vector3 yww() const; Vector3 zww() const; Vector3 www() const; + // 4-char swizzles + Vector4 xxxx() const; Vector4 yxxx() const; Vector4 zxxx() const; @@ -605,24 +671,33 @@ public: Vector4 zwww() const; Vector4 wwww() const; }; + inline Quat exp(const Quat& q) { return q.exp(); } + inline Quat log(const Quat& q) { return q.log(); } + inline G3D::Quat operator*(double s, const G3D::Quat& q) { return q * (float)s; } + inline G3D::Quat operator*(float s, const G3D::Quat& q) { return q * s; } + } // Namespace G3D + // Outside the namespace to avoid overloading confusion for C++ inline G3D::Quat pow(const G3D::Quat& q, double x) { return q.pow((float)x); } + + #include "Quat.inl" + #endif diff --git a/dep/include/g3dlite/G3D/Quat.inl b/dep/include/g3dlite/G3D/Quat.inl index 6b1805ec6e7..705cb0455d4 100644 --- a/dep/include/g3dlite/G3D/Quat.inl +++ b/dep/include/g3dlite/G3D/Quat.inl @@ -1,28 +1,38 @@ /** Quat.inl - @cite Quaternion implementation based on Watt & Watt page 363. + + @cite Quaternion implementation based on Watt & Watt page 363. Thanks to Max McGuire for slerp optimizations. + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2002-01-23 @edited 2004-03-04 */ + namespace G3D { + inline float& Quat::operator[] (int i) { debugAssert(i >= 0); debugAssert(i < 4); return ((float*)this)[i]; } + inline const float& Quat::operator[] (int i) const { debugAssert(i >= 0); debugAssert(i < 4); return ((float*)this)[i]; } + + inline Quat Quat::operator-(const Quat& other) const { return Quat(x - other.x, y - other.y, z - other.z, w - other.w); } + inline Quat Quat::operator+(const Quat& other) const { return Quat(x + other.x, y + other.y, z + other.z, w + other.w); } + } diff --git a/dep/include/g3dlite/G3D/Ray.h b/dep/include/g3dlite/G3D/Ray.h index b44796420f0..3929cf1e6ac 100644 --- a/dep/include/g3dlite/G3D/Ray.h +++ b/dep/include/g3dlite/G3D/Ray.h @@ -1,16 +1,23 @@ /** @file Ray.h + Ray class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2002-07-12 @edited 2006-02-21 */ + #ifndef G3D_RAY_H #define G3D_RAY_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Triangle.h" + namespace G3D { + /** A 3D Ray. */ @@ -20,23 +27,30 @@ private: this->origin = origin; this->direction = direction; } + public: Vector3 origin; + /** Not unit length */ Vector3 direction; + Ray() : origin(Vector3::zero()), direction(Vector3::zero()) {} + virtual ~Ray() {} + /** Creates a Ray from a origin and a (nonzero) direction. */ static Ray fromOriginAndDirection(const Vector3& point, const Vector3& direction) { return Ray(point, direction); } + Ray unit() const { return Ray(origin, direction.unit()); } + /** Returns the closest point on the Ray to point. */ @@ -48,33 +62,43 @@ public: return this->origin + direction * t; } } + /** Returns the closest distance between point and the Ray */ float distance(const Vector3& point) const { return (closestPoint(point) - point).magnitude(); } + /** Returns the point where the Ray and plane intersect. If there is no intersection, returns a point at infinity. + Planes are considered one-sided, so the ray will not intersect a plane where the normal faces in the traveling direction. */ Vector3 intersection(const class Plane& plane) const; + /** Returns the distance until intersection with the (solid) sphere. Will be 0 if inside the sphere, inf if there is no intersection. + The ray direction is <B>not</B> normalized. If the ray direction has unit length, the distance from the origin to intersection is equal to the time. If the direction does not have unit length, the distance = time * direction.length(). + See also the G3D::CollisionDetection "movingPoint" methods, which give more information about the intersection. */ float intersectionTime(const class Sphere& sphere) const; + float intersectionTime(const class Plane& plane) const; + float intersectionTime(const class Box& box) const; + float intersectionTime(const class AABox& box) const; + /** The three extra arguments are the weights of vertices 0, 1, and 2 at the intersection point; they are useful for texture mapping @@ -84,6 +108,7 @@ public: const Vector3& v0, const Vector3& v1, const Vector3& v2, const Vector3& edge01, const Vector3& edge02, double& w0, double& w1, double& w2) const; + /** Ray-triangle intersection for a 1-sided triangle. Fastest version. @cite http://www.acm.org/jgt/papers/MollerTrumbore97/ @@ -96,13 +121,16 @@ public: const Vector3& edge01, const Vector3& edge02) const; + inline float intersectionTime( const Vector3& vert0, const Vector3& vert1, const Vector3& vert2) const { + return intersectionTime(vert0, vert1, vert2, vert1 - vert0, vert2 - vert0); } + inline float intersectionTime( const Vector3& vert0, const Vector3& vert1, @@ -110,8 +138,10 @@ public: double& w0, double& w1, double& w2) const { + return intersectionTime(vert0, vert1, vert2, vert1 - vert0, vert2 - vert0, w0, w1, w2); } + /* One-sided triangle */ inline float intersectionTime(const Triangle& triangle) const { @@ -119,6 +149,7 @@ public: triangle.vertex(0), triangle.vertex(1), triangle.vertex(2), triangle.edge01, triangle.edge02); } + inline float intersectionTime( const Triangle& triangle, double& w0, @@ -127,6 +158,7 @@ public: return intersectionTime(triangle.vertex(0), triangle.vertex(1), triangle.vertex(2), triangle.edge01, triangle.edge02, w0, w1, w2); } + /** Refracts about the normal using G3D::Vector3::refractionDirection and bumps the ray slightly from the newOrigin. */ @@ -135,6 +167,7 @@ public: const Vector3& normal, float iInside, float iOutside) const; + /** Reflects about the normal using G3D::Vector3::reflectionDirection and bumps the ray slightly from @@ -144,44 +177,58 @@ public: const Vector3& normal) const; }; + #define EPSILON 0.000001 #define CROSS(dest,v1,v2) \ dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \ dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \ dest[2]=v1[0]*v2[1]-v1[1]*v2[0]; + #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]) + #define SUB(dest,v1,v2) \ dest[0]=v1[0]-v2[0]; \ dest[1]=v1[1]-v2[1]; \ dest[2]=v1[2]-v2[2]; + inline float Ray::intersectionTime( const Vector3& vert0, const Vector3& vert1, const Vector3& vert2, const Vector3& edge1, const Vector3& edge2) const { + (void)vert1; (void)vert2; + // Barycenteric coords float u, v; + float tvec[3], pvec[3], qvec[3]; + // begin calculating determinant - also used to calculate U parameter CROSS(pvec, direction, edge2); + // if determinant is near zero, ray lies in plane of triangle const float det = DOT(edge1, pvec); + if (det < EPSILON) { return (float)inf(); } + // calculate distance from vert0 to ray origin SUB(tvec, origin, vert0); + // calculate U parameter and test bounds u = DOT(tvec, pvec); if ((u < 0.0f) || (u > det)) { // Hit the plane outside the triangle return (float)inf(); } + // prepare to test V parameter CROSS(qvec, tvec, edge1); + // calculate V parameter and test bounds v = DOT(direction, qvec); if ((v < 0.0f) || (u + v > det)) { @@ -189,8 +236,10 @@ inline float Ray::intersectionTime( return (float)inf(); } + // Case where we don't need correct (u, v): const float t = DOT(edge2, qvec); + if (t >= 0.0f) { // Note that det must be positive return t / det; @@ -200,6 +249,7 @@ inline float Ray::intersectionTime( } } + inline float Ray::intersectionTime( const Vector3& vert0, const Vector3& vert1, @@ -209,53 +259,70 @@ inline float Ray::intersectionTime( double& w0, double& w1, double& w2) const { + (void)vert1; (void)vert2; + // Barycenteric coords float u, v; + float tvec[3], pvec[3], qvec[3]; + // begin calculating determinant - also used to calculate U parameter CROSS(pvec, direction, edge2); + // if determinant is near zero, ray lies in plane of triangle const float det = DOT(edge1, pvec); + if (det < EPSILON) { return (float)inf(); } + // calculate distance from vert0 to ray origin SUB(tvec, origin, vert0); + // calculate U parameter and test bounds u = DOT(tvec, pvec); if ((u < 0.0f) || (u > det)) { // Hit the plane outside the triangle return (float)inf(); } + // prepare to test V parameter CROSS(qvec, tvec, edge1); + // calculate V parameter and test bounds v = DOT(direction, qvec); if ((v < 0.0f) || (u + v > det)) { // Hit the plane outside the triangle return (float)inf(); } + float t = DOT(edge2, qvec); + if (t >= 0) { const float inv_det = 1.0f / det; t *= inv_det; u *= inv_det; v *= inv_det; + w0 = (1.0f - u - v); w1 = u; w2 = v; + return t; } else { // We had to travel backwards in time to intersect return (float)inf(); } } + #undef EPSILON #undef CROSS #undef DOT #undef SUB + }// namespace + #endif diff --git a/dep/include/g3dlite/G3D/RegistryUtil.h b/dep/include/g3dlite/G3D/RegistryUtil.h index d5b114d9a87..85b5d0ab1be 100644 --- a/dep/include/g3dlite/G3D/RegistryUtil.h +++ b/dep/include/g3dlite/G3D/RegistryUtil.h @@ -1,22 +1,32 @@ /** @file RegistryUtil.h + @created 2006-04-06 @edited 2006-04-06 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_REGISTRYUTIL_H #define G3D_REGISTRYUTIL_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" + // This file is only used on Windows #ifdef G3D_WIN32 + #include <string> + namespace G3D { + /** Provides generalized Windows registry querying. + All key names are one string in the format: "[base key]\[sub-keys]\value" + [base key] can be any of the following: HKEY_CLASSES_ROOT HKEY_CURRENT_CONFIG @@ -26,38 +36,52 @@ namespace G3D { HKEY_PERFORMANCE_NLSTEXT HKEY_PERFORMANCE_TEXT HKEY_USERS + keyExists() should be used to validate a key before reading or writing to ensure that a debug assert or false return is for a different error. */ class RegistryUtil { + public: /** returns true if the key exists */ static bool keyExists(const std::string& key); + /** returns false if the key could not be read for any reason. */ static bool readInt32(const std::string& key, int32& valueData); + /** Reads an arbitrary amount of data from a binary registry key. returns false if the key could not be read for any reason. + @beta @param valueData pointer to the output buffer of sufficient size. Pass NULL as valueData in order to have available data size returned in dataSize. @param dataSize size of the output buffer. When NULL is passed for valueData, contains the size of available data on successful return. */ static bool readBytes(const std::string& key, uint8* valueData, uint32& dataSize); + /** returns false if the key could not be read for any reason. */ static bool readString(const std::string& key, std::string& valueData); + /** returns false if the key could not be written for any reason. */ static bool writeInt32(const std::string& key, int32 valueData); + /** Writes an arbitrary amount of data to a binary registry key. returns false if the key could not be written for any reason. + @param valueData pointer to the input buffer @param dataSize size of the input buffer that should be written */ static bool writeBytes(const std::string& key, const uint8* valueData, uint32 dataSize); + /** returns false if the key could not be written for any reason. */ static bool writeString(const std::string& key, const std::string& valueData); + }; + } // namespace G3D + #endif // G3D_WIN32 + #endif // G3D_REGISTRYTUIL_H diff --git a/dep/include/g3dlite/G3D/Sphere.h b/dep/include/g3dlite/G3D/Sphere.h index 3ab1b19c74a..122e4d41f65 100644 --- a/dep/include/g3dlite/G3D/Sphere.h +++ b/dep/include/g3dlite/G3D/Sphere.h @@ -1,48 +1,65 @@ /** @file Sphere.h + Sphere class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2004-07-05 */ + #ifndef G3D_SPHERE_H #define G3D_SPHERE_H + #include "G3D/platform.h" #include "G3D/Vector3.h" #include "G3D/Array.h" #include "G3D/Sphere.h" + namespace G3D { + /** Sphere. */ class Sphere { private: + static int32 dummy; + public: Vector3 center; float radius; + Sphere() { center = Vector3::zero(); radius = 0; } + Sphere( const Vector3& center, float radius) { + this->center = center; this->radius = radius; } + virtual ~Sphere() {} + bool operator==(const Sphere& other) const { return (center == other.center) && (radius == other.radius); } + bool operator!=(const Sphere& other) const { return !((center == other.center) && (radius == other.radius)); } + /** Returns true if point is less than or equal to radius away from the center. */ bool contains(const Vector3& point) const; + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -52,6 +69,7 @@ public: int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** @deprecated Use culledBy(Array<Plane>&) */ @@ -60,6 +78,7 @@ public: int numPlanes, int32& cullingPlaneIndex = dummy, const uint32 testMask = -1) const; + /** See AABox::culledBy */ @@ -68,6 +87,7 @@ public: int32& cullingPlaneIndex, const uint32 testMask, uint32& childMask) const; + /** Conservative culling test that does not produce a mask for children. */ @@ -76,25 +96,34 @@ public: int32& cullingPlaneIndex = dummy, const uint32 testMask = -1) const; virtual std::string toString() const; + float volume() const; + /** @deprecated */ float surfaceArea() const; + inline float area() const { return surfaceArea(); } + /** Uniformly distributed on the surface. */ Vector3 randomSurfacePoint() const; + /** Uniformly distributed on the interior (includes surface) */ Vector3 randomInteriorPoint() const; + void getBounds(class AABox& out) const; }; + } // namespace + inline unsigned int hashCode(const G3D::Sphere& sphere) { return (unsigned int)(hashCode(sphere.center) + (sphere.radius * 13)); } + #endif diff --git a/dep/include/g3dlite/G3D/System.h b/dep/include/g3dlite/G3D/System.h index 183faffcf93..ab5a8d60a76 100644 --- a/dep/include/g3dlite/G3D/System.h +++ b/dep/include/g3dlite/G3D/System.h @@ -1,41 +1,58 @@ /** @file System.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @cite Rob Wyatt http://www.gamasutra.com/features/wyatts_world/19990709/processor_detection_01.htm @cite Benjamin Jurke http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-ProcessorDetectionClass&forum=cotd&id=-1 @cite Michael Herf http://www.stereopsis.com/memcpy.html + @created 2003-01-25 @edited 2006-04-26 */ + #ifndef G3D_SYSTEM_H #define G3D_SYSTEM_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include <string> + #ifdef G3D_OSX # include <CoreServices/CoreServices.h> #endif + namespace G3D { + typedef double RealTime; + class System { public: + /** Called automatically by the other System routines.*/ static void init(); + /** Guarantees that the start of the array is aligned to the specified number of bytes. */ static void* alignedMalloc(size_t bytes, size_t alignment); + /** Uses pooled storage to optimize small allocations (1 byte to 5 kilobytes). Can be 10x to 100x faster than calling ::malloc or new. + The result must be freed with free. + Threadsafe on Win32. + @sa calloc realloc OutOfMemoryCallback free */ static void* malloc(size_t bytes); + static void* calloc(size_t n, size_t x); + /** @param size Size of memory that the system was trying to allocate @param recoverable If true, the system will attempt to allocate again @@ -45,6 +62,7 @@ public: error was recoverable. */ typedef bool (*OutOfMemoryCallback)(size_t size, bool recoverable); + /** When System::malloc fails to allocate memory because the system is out of memory, it invokes this handler (if it is not NULL). @@ -52,42 +70,54 @@ public: was trying to allocate when it ran out. If the callback returns true, System::malloc will attempt to allocate the memory again. If the callback returns false, then System::malloc will return NULL. + You can use outOfMemoryCallback to free data structures or to register the failure. */ static OutOfMemoryCallback outOfMemoryCallback; + /** Version of realloc that works with System::malloc. */ static void* realloc(void* block, size_t bytes); + /** Returns a string describing how well System::malloc is using its internal pooled storage. "heap" memory was slow to allocate; the other data sizes are comparatively fast.*/ static std::string mallocPerformance(); static void resetMallocPerformanceCounters(); + /** Returns a string describing the current usage of the buffer pools used for optimizing System::malloc. */ static std::string mallocStatus(); + /** Free data allocated with System::malloc. + Threadsafe on Win32. */ static void free(void* p); + /** Frees memory allocated with alignedMalloc. */ static void alignedFree(void* ptr); + /** An implementation of memcpy that may be up to 2x as fast as the C library one on some processors. Guaranteed to have the same behavior as memcpy in all cases. */ static void memcpy(void* dst, const void* src, size_t numBytes); + /** An implementation of memset that may be up to 2x as fast as the C library one on some processors. Guaranteed to have the same behavior as memset in all cases. */ static void memset(void* dst, uint8 value, size_t numBytes); + }; + } // namespace + #endif diff --git a/dep/include/g3dlite/G3D/Table.h b/dep/include/g3dlite/G3D/Table.h index c1da412f3f3..1d021daae2b 100644 --- a/dep/include/g3dlite/G3D/Table.h +++ b/dep/include/g3dlite/G3D/Table.h @@ -1,14 +1,18 @@ /** @file Table.h + Templated hash table class. + @maintainer Morgan McGuire, matrix@graphics3d.com @created 2001-04-22 @edited 2006-10-14 Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_TABLE_H #define G3D_TABLE_H + #include "G3D/platform.h" #include "G3D/Array.h" #include "G3D/debug.h" @@ -17,71 +21,89 @@ #include "G3D/Crypto.h" #include <cstddef> #include <string> + #ifdef G3D_WIN32 # pragma warning (push) // Debug name too long warning # pragma warning (disable : 4786) #endif + template<typename Key> struct GHashCode{}; + template <> struct GHashCode<int> { size_t operator()(int key) const { return static_cast<size_t>(key); } }; + template <> struct GHashCode<G3D::uint32> { size_t operator()(G3D::uint32 key) const { return static_cast<size_t>(key); } }; + template <> struct GHashCode<G3D::uint64> { size_t operator()(G3D::uint64 key) const { return static_cast<size_t>(key); } }; + template <> struct GHashCode<void*> { size_t operator()(const void* key) const { return reinterpret_cast<size_t>(key); } }; + template<class T> struct GHashCode<T*> { size_t operator()(const T* key) const { return reinterpret_cast<size_t>(key); } }; + template <> struct GHashCode<const std::string> { size_t operator()(const std::string& key) const { return static_cast<size_t>(G3D::Crypto::crc32(key.c_str(), key.size())); } }; + template <> struct GHashCode<std::string> { size_t operator()(const std::string& key) const { return static_cast<size_t>(G3D::Crypto::crc32(key.c_str(), key.size())); } }; + namespace G3D { + /** An unordered data structure mapping keys to values. + Key must be a pointer, an int, a std::string, a class with a hashCode() method, or provide overloads for: + <PRE> template<> struct GHashCode<class Key> { size_t operator()(Key key) const { return reinterpret_cast<size_t>( ... ); } }; + bool operator==(const Key&, const Key&); </PRE> + G3D pre-defines GHashCode functions for common types (like <CODE>int</CODE> and <CODE>std::string</CODE>). If you use a Table with a different type you must write those functions yourself. For example, an enum would use: + <PRE> template<> struct GHashCode<MyEnum> { size_t operator()(MyEnum key) const { return reinterpret_cast<size_t>( key ); } }; </PRE> + And rely on the default enum operator==. + Periodically check that debugGetLoad() is low (> 0.1). When it gets near 1.0 your hash function is badly designed and maps too many inputs to the same output. @@ -89,6 +111,7 @@ namespace G3D { template<class Key, class Value, class HashFunc = GHashCode<Key> > class Table { public: + /** The pairs returned by iterator. */ @@ -97,6 +120,7 @@ public: Key key; Value value; }; + private: /** Linked list nodes used internally by HashTable. @@ -107,20 +131,24 @@ private: Entry entry; Node* next; + /** Provide pooled allocation for speed. */ inline void* operator new (size_t size) { return System::malloc(size); } + inline void operator delete (void* p) { System::free(p); } + Node(Key key, Value value, size_t hashCode, Node* next) { this->entry.key = key; this->entry.value = value; this->hashCode = hashCode; this->next = next; } + /** Clones a whole chain; */ @@ -128,42 +156,54 @@ private: return new Node(this->entry.key, this->entry.value, hashCode, (next == NULL) ? NULL : next->clone()); } }; + HashFunc m_HashFunc; + /** Number of elements in the table. */ size_t _size; + /** Array of Node*. We don't use Array<Node*> because Table is lower level. Some elements may be NULL. */ Node** bucket; + /** Length of the bucket array. */ size_t numBuckets; + /** Re-hashes for a larger bucket size. */ void resize(size_t numBuckets) { + Node** oldBucket = bucket; bucket = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16); System::memset(bucket, 0, sizeof(Node*) * numBuckets); + for (size_t b = 0; b < this->numBuckets; b++) { Node* node = oldBucket[b]; + while (node != NULL) { Node* nextNode = node->next; + // insert at the head of the list for bucket[i] size_t i = node->hashCode % numBuckets; node->next = bucket[i]; bucket[i] = node; + node = nextNode; } } + System::alignedFree(oldBucket); this->numBuckets = numBuckets; } + void copyFrom(const Table<Key, Value>& h) { this->_size = h._size; this->numBuckets = h.numBuckets; @@ -175,6 +215,7 @@ private: } } } + /** Frees the heap structures for the nodes. */ @@ -192,7 +233,9 @@ private: numBuckets = 0; _size = 0; } + public: + /** Creates an empty hash table. This causes some heap allocation to occur. */ @@ -202,6 +245,7 @@ public: bucket = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16); System::memset(bucket, 0, sizeof(Node*) * numBuckets); } + /** Destroys all of the memory allocated by the table, but does <B>not</B> call delete on keys or values if they are pointers. If you want to @@ -211,9 +255,11 @@ public: virtual ~Table() { freeMemory(); } + Table(const Table<Key, Value>& h) { this->copyFrom(h); } + Table& operator=(const Table<Key, Value>& h) { // No need to copy if the argument is this if (this != &h) { @@ -223,11 +269,13 @@ public: } return *this; } + /** Returns the length of the deepest bucket. */ size_t debugGetDeepestBucketSize() const { size_t deepest = 0; + for (size_t b = 0; b < numBuckets; b++) { size_t count = 0; Node* node = bucket[b]; @@ -235,12 +283,15 @@ public: node = node->next; ++count; } + if (count > deepest) { deepest = count; } } + return deepest; } + /** A small load (close to zero) means the hash table is acting very efficiently most of the time. A large load (close to 1) means @@ -251,22 +302,26 @@ public: double debugGetLoad() const { return debugGetDeepestBucketSize() / (double)size(); } + /** Returns the number of buckets. */ size_t debugGetNumBuckets() const { return numBuckets; } + /** C++ STL style iterator variable. See begin(). */ class Iterator { private: friend class Table<Key, Value>; + /** Bucket index. */ size_t index; + /** Linked list node. */ @@ -275,26 +330,31 @@ public: size_t numBuckets; Node** bucket; bool isDone; + /** Creates the end iterator. */ Iterator(const Table<Key, Value>* table) : table(const_cast<Table<Key, Value>*>(table)) { isDone = true; } + Iterator(const Table<Key, Value>* table, size_t numBuckets, Node** bucket) : table(const_cast<Table<Key, Value>*>(table)), numBuckets(numBuckets), bucket(bucket) { + if (numBuckets == 0) { // Empty table isDone = true; return; } + index = 0; node = bucket[index]; isDone = false; findNext(); } + /** Finds the next element, setting isDone if one can't be found. Looks at the current element first. @@ -310,10 +370,12 @@ public: } } } + public: inline bool operator!=(const Iterator& other) const { return !(*this == other); } + bool operator==(const Iterator& other) const { if (other.isDone || isDone) { // Common case; check against isDone. @@ -325,6 +387,7 @@ public: (index == other.index); } } + /** Pre increment. */ @@ -333,6 +396,7 @@ public: findNext(); return *this; } + /** Post increment (slower than preincrement). */ @@ -341,17 +405,21 @@ public: ++(*this); return old; } + const Entry& operator*() const { return node->entry; } + Entry* operator->() const { return &(node->entry); } + operator Entry*() const { return &(node->entry); } }; + /** C++ STL style iterator method. Returns the first Entry, which contains a key and value. Use preincrement (++entry) to get to @@ -360,6 +428,7 @@ public: Iterator begin() const { return Iterator(this, numBuckets, bucket); } + /** C++ STL style iterator method. Returns one after the last iterator element. @@ -367,6 +436,7 @@ public: const Iterator end() const { return Iterator(this); } + /** Removes all elements */ @@ -378,6 +448,7 @@ public: System::memset(bucket, 0, sizeof(Node*) * numBuckets); } + /** Returns the number of keys. */ @@ -385,6 +456,7 @@ public: return _size; } + /** If you insert a pointer into the key or value of a table, you are responsible for deallocating the object eventually. Inserting @@ -393,53 +465,68 @@ public: void set(const Key& key, const Value& value) { size_t code = m_HashFunc(key); size_t b = code % numBuckets; + // Go to the bucket Node* n = bucket[b]; + // No bucket, so this must be the first if (n == NULL) { bucket[b] = new Node(key, value, code, NULL); ++_size; return; } + size_t bucketLength = 1; + // Sometimes a bad hash code will cause all elements // to collide. Detect this case and don't rehash when // it occurs; nothing good will come from the rehashing. bool allSameCode = true; + // Try to find the node do { allSameCode = allSameCode && (code == n->hashCode); + if ((code == n->hashCode) && (n->entry.key == key)) { // Replace the existing node. n->entry.value = value; return; } + n = n->next; ++bucketLength; } while (n != NULL); + const size_t maxBucketLength = 5; if ((bucketLength > maxBucketLength) & ! allSameCode && (numBuckets < _size * 20)) { // This bucket was really large; rehash if all elements // don't have the same hashcode the number of buckets is reasonable. resize(numBuckets * 2 + 1); } + // Not found; insert at the head. b = code % numBuckets; bucket[b] = new Node(key, value, code, bucket[b]); ++_size; } + /** Removes an element from the table if it is present. It is an error to remove an element that isn't present. */ void remove(const Key& key) { + size_t code = m_HashFunc(key); size_t b = code % numBuckets; + // Go to the bucket Node* n = bucket[b]; + // Make sure it was found alwaysAssertM(n != NULL, "Tried to remove a key that was not in the table."); + Node* previous = NULL; + // Try to find the node do { if ((code == n->hashCode) && (n->entry.key == key)) { @@ -454,31 +541,39 @@ public: --_size; return; } + previous = n; n = n->next; } while (n != NULL); + alwaysAssertM(false, "Tried to remove a key that was not in the table."); } + /** Returns the value associated with key. @deprecated Use get(key, val) or */ Value& get(const Key& key) const { + size_t code = m_HashFunc(key); size_t b = code % numBuckets; + Node* node = bucket[b]; + while (node != NULL) { if ((node->hashCode == code) && (node->entry.key == key)) { return node->entry.value; } node = node->next; } + debugAssertM(false, "Key not found"); // The next line is here just to make // a compiler warning go away. return node->entry.value; } + /** If the key is present in the table, val is set to the associated value and returns true. If the key is not present, returns false. @@ -486,7 +581,9 @@ public: bool get(const Key& key, Value& val) const { size_t code = m_HashFunc(key); size_t b = code % numBuckets; + Node* node = bucket[b]; + while (node != NULL) { if ((node->hashCode == code) && (node->entry.key == key)) { // found key @@ -495,25 +592,31 @@ public: } node = node->next; } + // Failed to find key return false; } + /** Returns true if key is in the table. */ bool containsKey(const Key& key) const { size_t code = m_HashFunc(key); size_t b = code % numBuckets; + Node* node = bucket[b]; + while (node != NULL) { if ((node->hashCode == code) && (node->entry.key == key)) { return true; } node = node->next; } + return false; } + /** Short syntax for get. */ @@ -521,6 +624,7 @@ public: return get(key); } + /** Returns an array of all of the keys in the table. You can iterate over the keys to get the values. @@ -530,6 +634,7 @@ public: getKeys(keyArray); return keyArray; } + void getKeys(Array<Key>& keyArray) const { keyArray.resize(0, DONT_SHRINK_UNDERLYING_ARRAY); for (size_t i = 0; i < numBuckets; i++) { @@ -540,10 +645,13 @@ public: } } } + /** Calls delete on all of the keys. Does not clear the table, however, so you are left with a table of dangling pointers. + Same as <CODE>getKeys().deleteAll();</CODE> + To delete all of the values, you may want something like <PRE> Array<Key> keys = table.getKeys(); @@ -558,10 +666,12 @@ public: void deleteKeys() { getKeys().deleteAll(); } + /** Calls delete on all of the values. This is unsafe-- do not call unless you know that each value appears at most once. + Does not clear the table, so you are left with a table of dangling pointers. */ @@ -575,9 +685,12 @@ public: } } }; + } // namespace + #ifdef G3D_WIN32 # pragma warning (pop) #endif + #endif diff --git a/dep/include/g3dlite/G3D/Triangle.h b/dep/include/g3dlite/G3D/Triangle.h index 146fa0b6455..6852dac9492 100644 --- a/dep/include/g3dlite/G3D/Triangle.h +++ b/dep/include/g3dlite/G3D/Triangle.h @@ -1,20 +1,28 @@ /** @file Triangle.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2003-04-05 @edited 2004-03-14 + @cite Random point method by Greg Turk, Generating random points in triangles. In A. S. Glassner, ed., Graphics Gems, pp. 24-28. Academic Press, 1990 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_TRIANGLE_H #define G3D_TRIANGLE_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include "G3D/Vector3.h" #include "G3D/Plane.h" #include <string> + namespace G3D { + /** A generic triangle representation. This should not be used as the underlying triangle for creating models; it is intended @@ -25,37 +33,54 @@ class Triangle { private: friend class CollisionDetection; friend class Ray; + Vector3 _vertex[3]; + /** edgeDirection[i] is the normalized vector v[i+1] - v[i] */ Vector3 edgeDirection[3]; double edgeMagnitude[3]; Plane _plane; Vector3::Axis _primaryAxis; + /** vertex[1] - vertex[0] */ Vector3 edge01; /** vertex[2] - vertex[0] */ Vector3 edge02; + float _area; + void init(const Vector3& v0, const Vector3& v1, const Vector3& v2); + public: + Triangle(); + Triangle(const Vector3& v0, const Vector3& v1, const Vector3& v2); + ~Triangle(); + /** 0, 1, or 2 */ inline const Vector3& vertex(int n) const { debugAssert((n >= 0) && (n < 3)); return _vertex[n]; } + double area() const; + Vector3::Axis primaryAxis() const { return _primaryAxis; } + const Vector3& normal() const; + /** Barycenter */ Vector3 center() const; + const Plane& plane() const; + /** Returns a random point in the triangle. */ Vector3 randomPoint() const; + /** For two triangles to be equal they must have the same vertices <I>in the same order</I>. @@ -67,19 +92,26 @@ public: return false; } } + return true; } + inline unsigned int hashCode() const { return _vertex[0].hashCode() + (_vertex[1].hashCode() >> 2) + _vertex[2].hashCode(); } + void getBounds(class AABox&) const; + }; + } // namespace + inline unsigned int hashCode(const G3D::Triangle& t) { return t.hashCode(); } + #endif diff --git a/dep/include/g3dlite/G3D/Vector2.h b/dep/include/g3dlite/G3D/Vector2.h index 813ef22c731..3d66e654f93 100644 --- a/dep/include/g3dlite/G3D/Vector2.h +++ b/dep/include/g3dlite/G3D/Vector2.h @@ -1,22 +1,30 @@ /** @file Vector2.h + 2D vector class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2006-01-14 Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_VECTOR2_H #define G3D_VECTOR2_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include "Vector2int16.h" #include <string> + namespace G3D { + class Vector2; class Vector3; class Vector4; + /** Do not subclass-- this implementation makes assumptions about the memory layout. @@ -28,9 +36,11 @@ private: bool operator>(const Vector2&) const; bool operator<=(const Vector2&) const; bool operator>=(const Vector2&) const; + public: // coordinates float x, y; + // construction Vector2(); Vector2(float x, float y); @@ -38,10 +48,12 @@ public: Vector2(double coordinate[2]); Vector2(const Vector2& rkVector); Vector2(const class Vector2int16& v); + float& operator[] (int i); const float& operator[] (int i) const; operator float* (); operator const float* () const; + // assignment and comparison Vector2& operator= (const Vector2& rkVector); bool operator== (const Vector2& rkVector) const; @@ -51,10 +63,13 @@ public: bool fuzzyNe(const Vector2& other) const; /** Returns true if this vector has finite length */ bool isFinite() const; + /** Returns true if this vector has length == 0 */ bool isZero() const; + /** Returns true if this vector has length == 1 */ bool isUnit() const; + // arithmetic operations Vector2 operator+ (const Vector2& rkVector) const; Vector2 operator- (const Vector2& rkVector) const; @@ -63,25 +78,30 @@ public: Vector2 operator/ (const Vector2& rkVector) const; Vector2 operator/ (float fScalar) const; Vector2 operator- () const; + inline float sum() const { return x + y; } + /** Linear interpolation */ inline Vector2 lerp(const Vector2& v, float alpha) const { return (*this) + (v - *this) * alpha; } + inline Vector2 clamp(const Vector2& low, const Vector2& high) const { return Vector2( G3D::clamp(x, low.x, high.x), G3D::clamp(y, low.y, high.y)); } + inline Vector2 clamp(float low, float high) const { return Vector2( (float)G3D::clamp(x, low, high), (float)G3D::clamp(y, low, high)); } + // arithmetic updates Vector2& operator+= (const Vector2& rkVector); Vector2& operator-= (const Vector2& rkVector); @@ -89,6 +109,7 @@ public: Vector2& operator/= (float fScalar); Vector2& operator*= (const Vector2& rkVector); Vector2& operator/= (const Vector2& rkVector); + // vector operations float length() const; Vector2 direction() const; @@ -99,13 +120,17 @@ public: Vector2 fastDirection() const { return direction(); } + float squaredLength () const; float dot (const Vector2& rkVector) const; float unitize (float fTolerance = 1e-06); + Vector2 min(const Vector2 &v) const; Vector2 max(const Vector2 &v) const; + // Random unit vector static Vector2 random(); + // Special values. // Intentionally not inlined: see Matrix3::identity() for details. static const Vector2& zero(); @@ -119,6 +144,8 @@ public: /** Largest representable vector */ static const Vector2& maxFinite(); + + // Deprecated. See Matrix3::identity() for details. /** @deprecated Use Vector2::zero() */ static const Vector2 ZERO; @@ -126,13 +153,18 @@ public: static const Vector2 UNIT_S; /** @deprecated Use Vector2::unitY() */ static const Vector2 UNIT_T; + std::string toString() const; + // 2-char swizzles + Vector2 xx() const; Vector2 yx() const; Vector2 xy() const; Vector2 yy() const; + // 3-char swizzles + Vector3 xxx() const; Vector3 yxx() const; Vector3 xyx() const; @@ -141,7 +173,9 @@ public: Vector3 yxy() const; Vector3 xyy() const; Vector3 yyy() const; + // 4-char swizzles + Vector4 xxxx() const; Vector4 yxxx() const; Vector4 xyxx() const; @@ -158,102 +192,132 @@ public: Vector4 yxyy() const; Vector4 xyyy() const; Vector4 yyyy() const; + }; + inline Vector2 operator*(double s, const Vector2& v) { return v * (float)s; } + inline Vector2 operator*(float s, const Vector2& v) { return v * s; } + inline Vector2 operator*(int s, const Vector2& v) { return v * (float)s; } + inline unsigned int hashCode(const G3D::Vector2& v) { return v.hashCode(); } + inline Vector2::Vector2 () : x(0.0f), y(0.0f) { } + inline Vector2::Vector2(float _x, float _y) : x(_x), y(_y) { } + inline Vector2::Vector2 (float afCoordinate[2]) { x = afCoordinate[0]; y = afCoordinate[1]; } + + inline Vector2::Vector2 (double afCoordinate[2]) { x = (float)afCoordinate[0]; y = (float)afCoordinate[1]; } + inline Vector2::Vector2 (const Vector2& rkVector) { x = rkVector.x; y = rkVector.y; } + inline Vector2::Vector2 (const Vector2int16& v) : x(v.x), y(v.y) { } + inline float& Vector2::operator[] (int i) { return ((float*)this)[i]; } + inline const float& Vector2::operator[] (int i) const { return ((float*)this)[i]; } + inline Vector2::operator float* () { return (float*)this; } + inline Vector2::operator const float* () const { return (float*)this; } + inline Vector2& Vector2::operator= (const Vector2& rkVector) { x = rkVector.x; y = rkVector.y; return *this; } + inline bool Vector2::operator== (const Vector2& rkVector) const { return ( x == rkVector.x && y == rkVector.y); } + inline bool Vector2::operator!= (const Vector2& rkVector) const { return ( x != rkVector.x || y != rkVector.y); } + inline Vector2 Vector2::operator+ (const Vector2& rkVector) const { return Vector2(x + rkVector.x, y + rkVector.y); } + inline Vector2 Vector2::operator- (const Vector2& rkVector) const { return Vector2(x - rkVector.x, y - rkVector.y); } + inline Vector2 Vector2::operator* (float fScalar) const { return Vector2(fScalar*x, fScalar*y); } + + inline Vector2 Vector2::operator- () const { return Vector2( -x, -y); } + + inline Vector2& Vector2::operator+= (const Vector2& rkVector) { x += rkVector.x; y += rkVector.y; return *this; } + + inline Vector2& Vector2::operator-= (const Vector2& rkVector) { x -= rkVector.x; y -= rkVector.y; return *this; } + + inline Vector2& Vector2::operator*= (float fScalar) { x *= fScalar; y *= fScalar; @@ -261,36 +325,47 @@ inline Vector2& Vector2::operator*= (float fScalar) { } + + inline Vector2& Vector2::operator*= (const Vector2& rkVector) { x *= rkVector.x; y *= rkVector.y; return *this; } + + inline Vector2& Vector2::operator/= (const Vector2& rkVector) { x /= rkVector.x; y /= rkVector.y; return *this; } + inline Vector2 Vector2::operator* (const Vector2& rkVector) const { return Vector2(x * rkVector.x, y * rkVector.y); } + + inline Vector2 Vector2::operator/ (const Vector2& rkVector) const { return Vector2(x / rkVector.x, y / rkVector.y); } + inline float Vector2::squaredLength () const { return x*x + y*y; } + inline float Vector2::length () const { return sqrtf(x*x + y*y); } + inline Vector2 Vector2::direction () const { float lenSquared = x * x + y * y; + if (lenSquared != 1.0f) { return *this / sqrtf(lenSquared); } else { @@ -298,38 +373,56 @@ inline Vector2 Vector2::direction () const { } } + + inline float Vector2::dot (const Vector2& rkVector) const { return x*rkVector.x + y*rkVector.y; } + + inline Vector2 Vector2::min(const Vector2 &v) const { return Vector2(G3D::min(v.x, x), G3D::min(v.y, y)); } + + inline Vector2 Vector2::max(const Vector2 &v) const { return Vector2(G3D::max(v.x, x), G3D::max(v.y, y)); } + + inline bool Vector2::fuzzyEq(const Vector2& other) const { return G3D::fuzzyEq((*this - other).squaredLength(), 0); } + + inline bool Vector2::fuzzyNe(const Vector2& other) const { return G3D::fuzzyNe((*this - other).squaredLength(), 0); } + + inline bool Vector2::isFinite() const { return G3D::isFinite(x) && G3D::isFinite(y); } + + inline bool Vector2::isZero() const { return (x == 0.0f) && (y == 0.0f); } + + inline bool Vector2::isUnit() const { return squaredLength() == 1.0f; } + } + // Intentionally outside namespace to avoid operator overloading confusion inline G3D::Vector2 operator*(double s, const G3D::Vector2& v) { return v * (float)s; @@ -338,7 +431,9 @@ inline G3D::Vector2 operator*(int s, const G3D::Vector2& v) { return v * (float)s; } + inline unsigned int hashCode(const G3D::Vector2& v); + #endif diff --git a/dep/include/g3dlite/G3D/Vector2.inl b/dep/include/g3dlite/G3D/Vector2.inl index 8a39c703e91..27abecf02ce 100644 --- a/dep/include/g3dlite/G3D/Vector2.inl +++ b/dep/include/g3dlite/G3D/Vector2.inl @@ -1,15 +1,20 @@ /** @file Vector2.inl + @maintainer Morgan McGuire, matrix@graphics3d.com @cite Portions by Laura Wollstadt, graphics3d.com + @cite Portions based on Dave Eberly'x Magic Software Library at http://www.magic-software.com - + + @created 2001-06-02 @edited 2006-01-14 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + } diff --git a/dep/include/g3dlite/G3D/Vector2int16.h b/dep/include/g3dlite/G3D/Vector2int16.h index f6459085d0f..40f39bae43d 100644 --- a/dep/include/g3dlite/G3D/Vector2int16.h +++ b/dep/include/g3dlite/G3D/Vector2int16.h @@ -1,16 +1,23 @@ /** @file Vector2int16.h + @maintainer Morgan McGuire, matrix@brown.edu + @created 2003-08-09 @edited 2004-01-03 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef VECTOR2INT16_H #define VECTOR2INT16_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" + namespace G3D { + /** A Vector2 that packs its fields into uint16s. */ @@ -18,6 +25,7 @@ namespace G3D { // Switch to tight alignment #pragma pack(push, 2) #endif + class Vector2int16 { private: // Hidden operators @@ -25,35 +33,44 @@ private: bool operator>(const Vector2int16&) const; bool operator<=(const Vector2int16&) const; bool operator>=(const Vector2int16&) const; + public: G3D::int16 x; G3D::int16 y; + Vector2int16() : x(0), y(0) {} Vector2int16(G3D::int16 _x, G3D::int16 _y) : x(_x), y(_y){} Vector2int16(const class Vector2& v); + inline G3D::int16& operator[] (int i) { debugAssert(((unsigned int)i) <= 1); return ((G3D::int16*)this)[i]; } + inline const G3D::int16& operator[] (int i) const { debugAssert(((unsigned int)i) <= 1); return ((G3D::int16*)this)[i]; } + inline bool operator== (const Vector2int16& rkVector) const { return ((int32*)this)[0] == ((int32*)&rkVector)[0]; } + inline bool operator!= (const Vector2int16& rkVector) const { return ((int32*)this)[0] != ((int32*)&rkVector)[0]; } + } #if defined(G3D_LINUX) || defined(G3D_OSX) __attribute((aligned(1))) #endif ; + #ifdef G3D_WIN32 #pragma pack(pop) #endif + } #endif diff --git a/dep/include/g3dlite/G3D/Vector3.h b/dep/include/g3dlite/G3D/Vector3.h index 8b5a1576062..9f46bf87233 100644 --- a/dep/include/g3dlite/G3D/Vector3.h +++ b/dep/include/g3dlite/G3D/Vector3.h @@ -1,37 +1,49 @@ /** @file Vector3.h + 3D vector class + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2005-08-23 Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_VECTOR3_H #define G3D_VECTOR3_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include "G3D/Vector2.h" #include <iostream> #include <string> + namespace G3D { + class Vector2; class Vector3; class Vector4; + /** <B>Swizzles</B> Vector classes have swizzle operators, e.g. <CODE>v.xy()</CODE>, that allow selection of arbitrary sub-fields. These cannot be used as write masks. Examples + <PRE> Vector3 v(1, 2, 3); Vector3 j; Vector2 b; + b = v.xz(); j = b.xx(); </PRE> + <B>Warning</B> + Do not subclass-- this implementation makes assumptions about the memory layout. */ @@ -42,20 +54,25 @@ private: Note that if used for a collision or ray reflection you must negate the resulting vector to get a direction pointing <I>away</I> from the collision. + <PRE> V' N V + r ^ -, \ | / \|/ </PRE> + See also Vector3::reflectionDirection */ Vector3 reflectAbout(const Vector3& normal) const; + // Hidden operators bool operator<(const Vector3&) const; bool operator>(const Vector3&) const; bool operator<=(const Vector3&) const; bool operator>=(const Vector3&) const; + public: // construction Vector3(); @@ -65,8 +82,10 @@ public: Vector3(double coordinate[3]); Vector3(const Vector3& rkVector); Vector3(const class Vector3int16& v); + // coordinates float x, y, z; + // access vector V as V[0] = V.x, V[1] = V.y, V[2] = V.z // // WARNING. These member functions rely on @@ -74,18 +93,23 @@ public: // (2) the data packed in a 3*sizeof(float) memory block const float& operator[] (int i) const; float& operator[] (int i); + inline operator float* () { return (float*)this; } + operator const float* () const { return (float*)this; } + enum Axis {X_AXIS=0, Y_AXIS=1, Z_AXIS=2, DETECT_AXIS=-1}; + /** Returns the largest dimension. Particularly convenient for determining which plane to project a triangle onto for point-in-polygon tests. */ Axis primaryAxis() const; + // assignment and comparison Vector3& operator= (const Vector3& rkVector); bool operator== (const Vector3& rkVector) const; @@ -93,12 +117,16 @@ public: unsigned int hashCode() const; bool fuzzyEq(const Vector3& other) const; bool fuzzyNe(const Vector3& other) const; + /** Returns true if this vector has finite length. */ bool isFinite() const; + /** Returns true if this vector has length ~= 0 */ bool isZero() const; + /** Returns true if this vector has length ~= 1 */ bool isUnit() const; + // arithmetic operations Vector3 operator+ (const Vector3& v) const; Vector3 operator- (const Vector3& v) const; @@ -107,6 +135,7 @@ public: Vector3 operator* (const Vector3& v) const; Vector3 operator/ (const Vector3& v) const; Vector3 operator- () const; + // arithmetic updates Vector3& operator+= (const Vector3& v); Vector3& operator-= (const Vector3& v); @@ -114,24 +143,30 @@ public: Vector3& operator/= (float s); Vector3& operator*= (const Vector3& v); Vector3& operator/= (const Vector3& v); + /** @deprecated Use magnitude */ float G3D_DEPRECATED length() const; + float magnitude() const; + /** The result is a nan vector if the length is almost zero. */ Vector3 direction() const; + /** Potentially less accurate but faster than direction(). Only works if System::hasSSE is true. */ Vector3 fastDirection() const; + /** See also G3D::Ray::reflect. The length is 1. <PRE> V' N V + r ^ / \ | / \|'- @@ -139,6 +174,7 @@ public: */ Vector3 reflectionDirection(const Vector3& normal) const; + /** Returns Vector3::zero() if the length is nearly zero, otherwise returns a unit vector. @@ -153,6 +189,7 @@ public: return *this * (1.0f / mag); } } + /** Returns the direction of a refracted ray, where iExit is the index of refraction for the @@ -160,14 +197,19 @@ public: for the new material. Like Vector3::reflectionDirection, the result has length 1 and is pointed <I>away</I> from the intersection. + Returns Vector3::zero() in the case of total internal refraction. + @param iOutside The index of refraction (eta) outside (on the <I>positive</I> normal side) of the surface. + @param iInside The index of refraction (eta) inside (on the <I>negative</I> normal side) of the surface. + See also G3D::Ray::refract. <PRE> N V + ^ / | / |'- @@ -179,28 +221,37 @@ public: const Vector3& normal, float iInside, float iOutside) const; + /** Synonym for direction */ inline Vector3 unit() const { return direction(); } + /** Returns a normalized vector. May be computed with lower precision than unit */ inline Vector3 fastUnit() const { return fastDirection(); } + /** @deprecated Use squaredMagnitude */ float G3D_DEPRECATED squaredLength() const; + float squaredMagnitude () const; + /** @deprecated Use squaredMagnitude */ inline float G3D_DEPRECATED norm() const { return squaredMagnitude(); } + float dot(const Vector3& rkVector) const; + float G3D_DEPRECATED unitize(float fTolerance = 1e-06); + /** Cross product. Note that two cross products in a row can be computed more cheaply: v1 x (v2 x v3) = (v1 dot v3) v2 - (v1 dot v2) v3. */ Vector3 cross(const Vector3& rkVector) const; Vector3 unitCross (const Vector3& rkVector) const; + /** Returns a matrix such that v.cross() * w = v.cross(w). <PRE> @@ -210,53 +261,67 @@ public: </PRE> */ class Matrix3 cross() const; + Vector3 min(const Vector3 &v) const; Vector3 max(const Vector3 &v) const; + std::string toString() const; + inline Vector3 clamp(const Vector3& low, const Vector3& high) const { return Vector3( G3D::clamp(x, low.x, high.x), G3D::clamp(y, low.y, high.y), G3D::clamp(z, low.z, high.z)); } + inline Vector3 clamp(float low, float high) const { return Vector3( G3D::clamp(x, low, high), G3D::clamp(y, low, high), G3D::clamp(z, low, high)); } + /** Linear interpolation */ inline Vector3 lerp(const Vector3& v, float alpha) const { return (*this) + (v - *this) * alpha; } + /** Gram-Schmidt orthonormalization. */ static void orthonormalize (Vector3 akVector[3]); + /** Random unit vector, uniformly distributed */ static Vector3 random(); + /** Random unit vector, distributed so that the probability of V is proportional to max(V dot Normal, 0). + @cite Henrik Wann Jensen, Realistic Image Synthesis using Photon Mapping eqn 2.24 */ static Vector3 cosRandom(const Vector3& normal); + /** Random vector distributed over the hemisphere about normal. */ static Vector3 hemiRandom(const Vector3& normal); + // Input W must be initialize to a nonzero vector, output is {U,V,W} // an orthonormal basis. A hint is provided about whether or not W // is already unit length. static void generateOrthonormalBasis (Vector3& rkU, Vector3& rkV, Vector3& rkW, bool bUnitLengthW = true); + inline float sum() const { return x + y + z; } + inline float average() const { return sum() / 3.0f; } + // Special values. inline static const Vector3& zero() { static Vector3 v(0, 0, 0); return v; } inline static const Vector3& one() { static Vector3 v(1, 1, 1); return v; } @@ -269,6 +334,7 @@ public: inline static const Vector3& minFinite(){ static Vector3 v(-FLT_MAX, -FLT_MAX, -FLT_MAX); return v; } /** Largest representable vector */ inline static const Vector3& maxFinite(){ static Vector3 v(FLT_MAX, FLT_MAX, FLT_MAX); return v; } + // Deprecated. See Matrix3::identity() for details. /** @deprecated Use Vector3::zero() */ static const Vector3 ZERO; @@ -284,7 +350,9 @@ public: static const Vector3 INF3; /** @deprecated Use Vector3::nan() */ static const Vector3 NAN3; + // 2-char swizzles + Vector2 xx() const; Vector2 yx() const; Vector2 zx() const; @@ -294,7 +362,9 @@ public: Vector2 xz() const; Vector2 yz() const; Vector2 zz() const; + // 3-char swizzles + Vector3 xxx() const; Vector3 yxx() const; Vector3 zxx() const; @@ -322,7 +392,9 @@ public: Vector3 xzz() const; Vector3 yzz() const; Vector3 zzz() const; + // 4-char swizzles + Vector4 xxxx() const; Vector4 yxxx() const; Vector4 zxxx() const; @@ -404,21 +476,30 @@ public: Vector4 xzzz() const; Vector4 yzzz() const; Vector4 zzzz() const; + /** A value that can be passed to ignore a parameter. Never look at the result of dummy. */ static Vector3 dummy; }; + inline G3D::Vector3 operator*(float s, const G3D::Vector3& v) { return v * s; } + inline G3D::Vector3 operator*(double s, const G3D::Vector3& v) { return v * (float)s; } + inline G3D::Vector3 operator*(int s, const G3D::Vector3& v) { return v * (float)s; } + std::ostream& operator<<(std::ostream& os, const Vector3&); + } + unsigned int hashCode(const G3D::Vector3& v); + #include "Vector3.inl" + #endif diff --git a/dep/include/g3dlite/G3D/Vector3.inl b/dep/include/g3dlite/G3D/Vector3.inl index 1bfeb5ed441..e2f328165bb 100644 --- a/dep/include/g3dlite/G3D/Vector3.inl +++ b/dep/include/g3dlite/G3D/Vector3.inl @@ -1,12 +1,16 @@ -/** +/** @file Vector3.inl + @maintainer Morgan McGuire, matrix@graphics3d.com + @cite Portions based on Dave Eberly's Magic Software Library at http://www.magic-software.com + @created 2001-06-02 @edited 2004-05-21 Copyright 2000-2004, Morgan McGuire. All rights reserved. */ + //---------------------------------------------------------------------------- #ifdef SSE // If you receive an error on this line, it is because you do not have the file @@ -19,38 +23,50 @@ // to get this file. # include <xmmintrin.h> #endif + inline unsigned int hashCode(const G3D::Vector3& v) { return v.hashCode(); } + namespace G3D { + //---------------------------------------------------------------------------- inline Vector3::Vector3() : x(0.0f), y(0.0f), z(0.0f) { } + //---------------------------------------------------------------------------- + inline Vector3::Vector3 (float fX, float fY, float fZ) : x(fX), y(fY), z(fZ) { } + //---------------------------------------------------------------------------- inline Vector3::Vector3 (float V[3]) : x(V[0]), y(V[1]), z(V[2]){ } //---------------------------------------------------------------------------- inline Vector3::Vector3 (double V[3]) : x((float)V[0]), y((float)V[1]), z((float)V[2]){ } + //---------------------------------------------------------------------------- inline Vector3::Vector3 (const Vector3& V) : x(V.x), y(V.y), z(V.z) { } + //---------------------------------------------------------------------------- + //inline Vector3::Vector3 (const __m128& m) { // Cast from SSE packed floats // *this = *(Vector3*)&m; //} + //---------------------------------------------------------------------------- inline const float& Vector3::operator[] (int i) const { return ((float*)this)[i]; } + inline float& Vector3::operator[] (int i) { return ((float*)this)[i]; } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator= (const Vector3& rkVector) { x = rkVector.x; @@ -58,49 +74,64 @@ inline Vector3& Vector3::operator= (const Vector3& rkVector) { z = rkVector.z; return *this; } + //---------------------------------------------------------------------------- + inline bool Vector3::fuzzyEq(const Vector3& other) const { return G3D::fuzzyEq((*this - other).squaredMagnitude(), 0); } + //---------------------------------------------------------------------------- + inline bool Vector3::fuzzyNe(const Vector3& other) const { return G3D::fuzzyNe((*this - other).squaredMagnitude(), 0); } + //---------------------------------------------------------------------------- + inline bool Vector3::isFinite() const { return G3D::isFinite(x) && G3D::isFinite(y) && G3D::isFinite(z); } + //---------------------------------------------------------------------------- inline bool Vector3::operator== (const Vector3& rkVector) const { return ( x == rkVector.x && y == rkVector.y && z == rkVector.z ); } + //---------------------------------------------------------------------------- inline bool Vector3::operator!= (const Vector3& rkVector) const { return ( x != rkVector.x || y != rkVector.y || z != rkVector.z ); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::operator+ (const Vector3& rkVector) const { return Vector3(x + rkVector.x, y + rkVector.y, z + rkVector.z); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::operator- (const Vector3& rkVector) const { return Vector3(x - rkVector.x, y - rkVector.y, z - rkVector.z); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::operator* (const Vector3& rkVector) const { return Vector3(x * rkVector.x, y * rkVector.y, z * rkVector.z); } + inline Vector3 Vector3::operator*(float f) const { return Vector3(x * f, y * f, z * f); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::operator/ (const Vector3& rkVector) const { return Vector3(x / rkVector.x, y / rkVector.y, z / rkVector.z); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::operator- () const { return Vector3(-x, -y, -z); } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator+= (const Vector3& rkVector) { x += rkVector.x; @@ -108,6 +139,7 @@ inline Vector3& Vector3::operator+= (const Vector3& rkVector) { z += rkVector.z; return *this; } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator-= (const Vector3& rkVector) { x -= rkVector.x; @@ -115,6 +147,7 @@ inline Vector3& Vector3::operator-= (const Vector3& rkVector) { z -= rkVector.z; return *this; } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator*= (float fScalar) { x *= fScalar; @@ -122,6 +155,7 @@ inline Vector3& Vector3::operator*= (float fScalar) { z *= fScalar; return *this; } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator*= (const Vector3& rkVector) { x *= rkVector.x; @@ -129,6 +163,7 @@ inline Vector3& Vector3::operator*= (const Vector3& rkVector) { z *= rkVector.z; return *this; } + //---------------------------------------------------------------------------- inline Vector3& Vector3::operator/= (const Vector3& rkVector) { x /= rkVector.x; @@ -136,43 +171,53 @@ inline Vector3& Vector3::operator/= (const Vector3& rkVector) { z /= rkVector.z; return *this; } + //---------------------------------------------------------------------------- inline float Vector3::squaredMagnitude () const { return x*x + y*y + z*z; } + //---------------------------------------------------------------------------- inline float Vector3::squaredLength () const { return squaredMagnitude(); } + //---------------------------------------------------------------------------- inline float Vector3::magnitude() const { return sqrtf(x*x + y*y + z*z); } + //---------------------------------------------------------------------------- inline float Vector3::length() const { return magnitude(); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::direction () const { float lenSquared = squaredMagnitude(); float invSqrt = 1.0f / sqrtf(lenSquared); return Vector3(x * invSqrt, y * invSqrt, z * invSqrt); } + //---------------------------------------------------------------------------- + inline Vector3 Vector3::fastDirection () const { float lenSquared = x * x + y * y + z * z; float invSqrt = rsq(lenSquared); return Vector3(x * invSqrt, y * invSqrt, z * invSqrt); } + //---------------------------------------------------------------------------- inline float Vector3::dot (const Vector3& rkVector) const { return x*rkVector.x + y*rkVector.y + z*rkVector.z; } + //---------------------------------------------------------------------------- inline Vector3 Vector3::cross (const Vector3& rkVector) const { return Vector3(y*rkVector.z - z*rkVector.y, z*rkVector.x - x*rkVector.z, x*rkVector.y - y*rkVector.x); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::unitCross (const Vector3& rkVector) const { Vector3 kCross(y*rkVector.z - z*rkVector.y, z*rkVector.x - x*rkVector.z, @@ -180,20 +225,26 @@ inline Vector3 Vector3::unitCross (const Vector3& rkVector) const { kCross.unitize(); return kCross; } + //---------------------------------------------------------------------------- inline Vector3 Vector3::min(const Vector3 &v) const { return Vector3(G3D::min(v.x, x), G3D::min(v.y, y), G3D::min(v.z, z)); } + //---------------------------------------------------------------------------- inline Vector3 Vector3::max(const Vector3 &v) const { return Vector3(G3D::max(v.x, x), G3D::max(v.y, y), G3D::max(v.z, z)); } + //---------------------------------------------------------------------------- inline bool Vector3::isZero() const { return G3D::fuzzyEq(squaredMagnitude(), 0.0f); } + //---------------------------------------------------------------------------- + inline bool Vector3::isUnit() const { return G3D::fuzzyEq(squaredMagnitude(), 1.0f); } + } // namespace diff --git a/dep/include/g3dlite/G3D/Vector3int16.h b/dep/include/g3dlite/G3D/Vector3int16.h index 84d8bb825de..e0631125960 100644 --- a/dep/include/g3dlite/G3D/Vector3int16.h +++ b/dep/include/g3dlite/G3D/Vector3int16.h @@ -1,16 +1,22 @@ /** @file Vector3int16.h + @maintainer Morgan McGuire, matrix@brown.edu + @created 2003-04-07 @edited 2003-06-24 Copyright 2000-2004, Morgan McGuire. All rights reserved. */ + #ifndef VECTOR3INT16_H #define VECTOR3INT16_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" + namespace G3D { + /** A Vector3 that packs its fields into uint16s. */ @@ -18,6 +24,7 @@ namespace G3D { // Switch to tight alignment #pragma pack(push, 2) #endif + class Vector3int16 { private: // Hidden operators @@ -25,10 +32,12 @@ private: bool operator>(const Vector3int16&) const; bool operator<=(const Vector3int16&) const; bool operator>=(const Vector3int16&) const; + public: G3D::int16 x; G3D::int16 y; G3D::int16 z; + Vector3int16() : x(0), y(0), z(0) {} Vector3int16(G3D::int16 _x, G3D::int16 _y, G3D::int16 _z) : x(_x), y(_y), z(_z) {} Vector3int16(const class Vector3& v); @@ -37,9 +46,11 @@ public: __attribute((aligned(1))) #endif ; + #ifdef G3D_WIN32 #pragma pack(pop) #endif + } #endif diff --git a/dep/include/g3dlite/G3D/Vector4.h b/dep/include/g3dlite/G3D/Vector4.h index ea8b83a5303..1bf243e5ed7 100644 --- a/dep/include/g3dlite/G3D/Vector4.h +++ b/dep/include/g3dlite/G3D/Vector4.h @@ -1,23 +1,32 @@ /** @file Vector4.h + Homogeneous vector class. + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2002-07-09 @edited 2005-03-28 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3D_VECTOR4_H #define G3D_VECTOR4_H + #include "G3D/platform.h" #include "G3D/g3dmath.h" #include "G3D/Vector3.h" #include "G3D/Vector2.h" #include <string> + namespace G3D { + class Vector2; class Vector3; class Vector4; + /** Do not subclass-- this implementation makes assumptions about the memory layout. @@ -29,6 +38,7 @@ private: bool operator>(const Vector4&) const; bool operator<=(const Vector4&) const; bool operator>=(const Vector4&) const; + public: // construction Vector4(); @@ -39,8 +49,10 @@ public: Vector4(const Vector3& rkVector, float fW); Vector4(const Vector2& v1, const Vector2& v2); Vector4(const Vector2& v1, float fz, float fw); + // coordinates float x, y, z, w; + // access vector V as V[0] = V.x, V[1] = V.y, V[2] = V.z, etc. // // WARNING. These member functions rely on @@ -50,63 +62,80 @@ public: const float& operator[] (int i) const; operator float* (); operator const float* () const; + // assignment and comparison Vector4& operator= (const Vector4& rkVector); bool operator== (const Vector4& rkVector) const; bool operator!= (const Vector4& rkVector) const; + inline void set(float _x, float _y, float _z, float _w) { x = _x; y = _y; z = _z; w = _w; } + inline void set(const Vector3& v, float _w) { x = v.x; y = v.y; z = v.z; w = _w; } + inline void set(const Vector2& v, float _z, float _w) { x = v.x; y = v.y; z = _z; w = _w; } + unsigned int hashCode() const; bool fuzzyEq(const Vector4& other) const; bool fuzzyNe(const Vector4& other) const; + inline static const Vector4& inf() { static Vector4 v((float)G3D::inf(), (float)G3D::inf(), (float)G3D::inf(), (float)G3D::inf()); return v; } inline static const Vector4& nan() { static Vector4 v((float)G3D::nan(), (float)G3D::nan(), (float)G3D::nan(), (float)G3D::nan()); return v; } + /** sqrt(this->dot(*this)) */ float length() const; float squaredLength() const; + inline float sum() const { return x + y + z + w; } + /** Returns true if this vector has finite length */ bool isFinite() const; + /** Returns true if this vector has length == 0 */ bool isZero() const; + /** Returns true if this vector has length == 1 */ bool isUnit() const; + // arithmetic operations Vector4 operator+ (const Vector4& rkVector) const; Vector4 operator- (const Vector4& rkVector) const; + inline Vector4 operator*(const Vector4& rkVector) const { return Vector4(x * rkVector.x, y * rkVector.y, z * rkVector.z, w * rkVector.w); } + inline Vector4 operator/(const Vector4& rkVector) const { return Vector4(x / rkVector.x, y / rkVector.y, z / rkVector.z, w / rkVector.w); } + Vector4 operator* (float fScalar) const; Vector4 operator/ (float fScalar) const; Vector4 operator- () const; friend Vector4 operator* (float, const Vector4& rkVector); + // arithmetic updates Vector4& operator+= (const Vector4& rkVector); Vector4& operator-= (const Vector4& rkVector); Vector4& operator*= (float fScalar); Vector4& operator/= (float fScalar); + inline Vector4 clamp(const Vector4& low, const Vector4& high) const { return Vector4( G3D::clamp(x, low.x, high.x), @@ -114,6 +143,7 @@ public: G3D::clamp(z, low.z, high.z), G3D::clamp(w, low.w, high.w)); } + inline Vector4 clamp(float low, float high) const { return Vector4( G3D::clamp(x, low, high), @@ -121,15 +151,21 @@ public: G3D::clamp(z, low, high), G3D::clamp(w, low, high)); } + float dot (const Vector4& rkVector) const; + Vector4 min(const Vector4& v) const; Vector4 max(const Vector4& v) const; + std::string toString() const; + /** Linear interpolation */ Vector4 lerp(const Vector4& v, float alpha) const; + // 2-char swizzles + Vector2 xx() const; Vector2 yx() const; Vector2 zx() const; @@ -146,7 +182,9 @@ public: Vector2 yw() const; Vector2 zw() const; Vector2 ww() const; + // 3-char swizzles + Vector3 xxx() const; Vector3 yxx() const; Vector3 zxx() const; @@ -211,7 +249,9 @@ public: Vector3 yww() const; Vector3 zww() const; Vector3 www() const; + // 4-char swizzles + Vector4 xxxx() const; Vector4 yxxx() const; Vector4 zxxx() const; @@ -468,12 +508,18 @@ public: Vector4 ywww() const; Vector4 zwww() const; Vector4 wwww() const; + }; + } + inline G3D::Vector4 operator* (float s, const G3D::Vector4& v) { return v * s; } + unsigned int hashCode(const G3D::Vector4& v); + #include "Vector4.inl" + #endif diff --git a/dep/include/g3dlite/G3D/Vector4.inl b/dep/include/g3dlite/G3D/Vector4.inl index 324d519d836..48ebf542723 100644 --- a/dep/include/g3dlite/G3D/Vector4.inl +++ b/dep/include/g3dlite/G3D/Vector4.inl @@ -1,25 +1,34 @@ -/** +/** @file Vector4.inl + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2002-07-09 @edited 2003-02-10 */ + //---------------------------------------------------------------------------- + inline unsigned int hashCode(const G3D::Vector4& v) { return v.hashCode(); } + namespace G3D { + //---------------------------------------------------------------------------- inline Vector4::Vector4() { x = y = z = w = 0; } + //---------------------------------------------------------------------------- + inline Vector4::Vector4 (float fX, float fY, float fZ, float fW) { x = fX; y = fY; z = fZ; w = fW; } + //---------------------------------------------------------------------------- inline Vector4::Vector4 (float afCoordinate[4]) { x = afCoordinate[0]; @@ -27,6 +36,7 @@ inline Vector4::Vector4 (float afCoordinate[4]) { z = afCoordinate[2]; w = afCoordinate[3]; } + //---------------------------------------------------------------------------- inline Vector4::Vector4(const Vector4& rkVector) { x = rkVector.x; @@ -41,21 +51,26 @@ inline Vector4::Vector4(const Vector3& rkVector, float fW) { z = rkVector.z; w = fW; } + //---------------------------------------------------------------------------- inline float& Vector4::operator[] (int i) { return ((float*)this)[i]; } + //---------------------------------------------------------------------------- inline const float& Vector4::operator[] (int i) const { return ((float*)this)[i]; } + //---------------------------------------------------------------------------- inline Vector4::operator float* () { return (float*)this; } + inline Vector4::operator const float* () const { return (float*)this; } + //---------------------------------------------------------------------------- inline Vector4& Vector4::operator= (const Vector4& rkVector) { x = rkVector.x; @@ -64,30 +79,37 @@ inline Vector4& Vector4::operator= (const Vector4& rkVector) { w = rkVector.w; return *this; } + //---------------------------------------------------------------------------- inline bool Vector4::operator== (const Vector4& rkVector) const { return ( (x == rkVector.x) && (y == rkVector.y) && (z == rkVector.z) && (w == rkVector.w)); } + //---------------------------------------------------------------------------- inline bool Vector4::operator!= (const Vector4& rkVector) const { return ( x != rkVector.x || y != rkVector.y || z != rkVector.z || w != rkVector.w); } + //---------------------------------------------------------------------------- inline Vector4 Vector4::operator+ (const Vector4& rkVector) const { return Vector4(x + rkVector.x, y + rkVector.y, z + rkVector.z, w + rkVector.w); } + //---------------------------------------------------------------------------- inline Vector4 Vector4::operator- (const Vector4& rkVector) const { return Vector4(x - rkVector.x, y - rkVector.y, z - rkVector.z, w - rkVector.w); } + //---------------------------------------------------------------------------- inline Vector4 Vector4::operator* (float fScalar) const { return Vector4(fScalar*x, fScalar*y, fScalar*z, fScalar*w); } + //---------------------------------------------------------------------------- inline Vector4 Vector4::operator- () const { return Vector4( -x, -y, -z, -w); } + //---------------------------------------------------------------------------- inline Vector4& Vector4::operator+= (const Vector4& rkVector) { x += rkVector.x; @@ -96,6 +118,7 @@ inline Vector4& Vector4::operator+= (const Vector4& rkVector) { w += rkVector.w; return *this; } + //---------------------------------------------------------------------------- inline Vector4& Vector4::operator-= (const Vector4& rkVector) { x -= rkVector.x; @@ -104,11 +127,14 @@ inline Vector4& Vector4::operator-= (const Vector4& rkVector) { w -= rkVector.w; return *this; } + //---------------------------------------------------------------------------- + inline Vector4 Vector4::lerp(const Vector4& v, float alpha) const { - return (*this) + (v - *this) * alpha; + return (*this) + (v - *this) * alpha; } + //---------------------------------------------------------------------------- inline Vector4& Vector4::operator*= (float fScalar) { x *= fScalar; @@ -118,37 +144,50 @@ inline Vector4& Vector4::operator*= (float fScalar) { return *this; } + //---------------------------------------------------------------------------- inline float Vector4::dot(const Vector4& rkVector) const { return x*rkVector.x + y*rkVector.y + z*rkVector.z + w*rkVector.w; } + //---------------------------------------------------------------------------- inline Vector4 Vector4::min(const Vector4 &v) const { return Vector4(G3D::min(v.x, x), G3D::min(v.y, y), G3D::min(v.z, z), G3D::min(v.w, w)); } + //---------------------------------------------------------------------------- inline Vector4 Vector4::max(const Vector4 &v) const { return Vector4(G3D::max(v.x, x), G3D::max(v.y, y), G3D::max(v.z, z), G3D::max(v.w, w)); } + //---------------------------------------------------------------------------- inline bool Vector4::isZero() const { return (x == 0.0f) && (y == 0.0f) && (z == 0.0f) && (w == 0.0f); } + //---------------------------------------------------------------------------- + inline bool Vector4::isFinite() const { return G3D::isFinite(x) && G3D::isFinite(y) && G3D::isFinite(z) && G3D::isFinite(w); } + //---------------------------------------------------------------------------- + inline bool Vector4::isUnit() const { return squaredLength() == 1.0; } + //---------------------------------------------------------------------------- + inline float Vector4::length() const { return sqrtf(squaredLength()); } + //---------------------------------------------------------------------------- + inline float Vector4::squaredLength() const { return x * x + y * y + z * z + w * w; } + } diff --git a/dep/include/g3dlite/G3D/debug.h b/dep/include/g3dlite/G3D/debug.h index e889eff31a8..408dd3ea146 100644 --- a/dep/include/g3dlite/G3D/debug.h +++ b/dep/include/g3dlite/G3D/debug.h @@ -1,9 +1,12 @@ #ifndef G3D_LITE_DEBUG_H #define G3D_LITE_DEBUG_H + #define debugStatement(x) #define debugAssert(x) #define debugAssertM(x, y) #define alwaysAssertM(x, y) + #endif + diff --git a/dep/include/g3dlite/G3D/format.h b/dep/include/g3dlite/G3D/format.h index b04c9cfab76..fd129381791 100644 --- a/dep/include/g3dlite/G3D/format.h +++ b/dep/include/g3dlite/G3D/format.h @@ -1,13 +1,18 @@ /** @file format.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @author 2000-09-09 @edited 2005-11-03 + Copyright 2000-2005, Morgan McGuire. All rights reserved. */ + #ifndef G3D_FORMAT_H #define G3D_FORMAT_H + #include "G3D/platform.h" #include <string> #include <stdio.h> @@ -19,12 +24,15 @@ //#include <varargs.h> #include <stdarg.h> #endif + #ifndef _MSC_VER #ifndef __cdecl #define __cdecl __attribute__((cdecl)) #endif #endif + namespace G3D { + /** Produces a string from arguments of the style of printf. This avoids problems with buffer overflows when using sprintf and makes it easy @@ -35,6 +43,7 @@ namespace G3D { std::string format( const char* fmt ...) G3D_CHECK_PRINTF_ARGS; + /** Like format, but can be called with the argument list from a ... function. */ @@ -42,6 +51,8 @@ std::string vformat( const char* fmt, va_list argPtr) G3D_CHECK_VPRINTF_ARGS; + }; // namespace + #endif diff --git a/dep/include/g3dlite/G3D/g3dmath.h b/dep/include/g3dlite/G3D/g3dmath.h index 6005d717482..38ee23fc3c1 100644 --- a/dep/include/g3dlite/G3D/g3dmath.h +++ b/dep/include/g3dlite/G3D/g3dmath.h @@ -1,15 +1,21 @@ /** @file g3dmath.h + Math util class. + @maintainer Morgan McGuire, matrix@graphics3d.com @cite highestBit by Jukka Liimatta + @created 2001-06-02 @edited 2006-01-16 + Copyright 2000-2006, Morgan McGuire. All rights reserved. */ + #ifndef G3DMATH_H #define G3DMATH_H + #ifdef _MSC_VER // Disable conditional expression is constant, which occurs incorrectly on inlined functions # pragma warning (push) @@ -17,70 +23,96 @@ // disable: "C++ exception handler used" # pragma warning (disable : 4530) #endif + #include "G3D/platform.h" #include <ctype.h> #include <string> #include <float.h> #include <limits> + /*These defines enable functionality introduced with the 1999 ISO C **standard. They must be defined before the inclusion of math.h to **engage them. If optimisation is enabled, these functions will be **inlined. With optimisation switched off, you have to link in the **maths library using -lm. */ + #define _ISOC9X_SOURCE1 #define _ISOC99_SOURCE1 #define __USE_ISOC9X1 #define __USE_ISOC991 + #include <math.h> + #include "G3D/debug.h" + #undef min #undef max + namespace G3D { + #if defined(_MSC_VER) + #if !defined(_WIN64) + /** Win32 implementation of the C99 fast rounding routines. + @cite routines are Copyright (C) 2001 Erik de Castro Lopo <erikd AT mega-nerd DOT com> + Permission to use, copy, modify, distribute, and sell this file for any purpose is hereby granted without fee, provided that the above copyright and this permission notice appear in all copies. No representations are made about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty. */ + __inline long int lrint (double flt) { int intgr; + _asm { fld flt fistp intgr }; + return intgr; } + __inline long int lrintf(float flt) { int intgr; + _asm { fld flt fistp intgr }; + return intgr; } + #else + __inline long int lrint (double flt) { return (long int)floor(flt+0.5f); } + __inline long int lrintf(float flt) { return (long int)floorf(flt+0.5f); } + #endif + #endif + const double fuzzyEpsilon = 0.00001; + /** Returns a reference to a static double. This value should not be tested against directly, instead G3D::isNan() and G3D::isFinite() will return reliable results. */ inline const double& inf() { + // We already have <limits> included but // not using it in older gcc for safe compilations #if (__GNUC__ == 2) @@ -91,10 +123,12 @@ inline const double& inf() { #endif return i; } + /** Returns a reference to a static double. This value should not be tested against directly, instead G3D::isNan() and G3D::isFinite() will return reliable results. */ inline const double& nan() { + // We already have <limits> included but // not using it in older gcc for safe compilations #if (__GNUC__ == 2) @@ -105,21 +139,25 @@ inline const double& nan() { #endif return n; } + /** Returns a reference to a static double. Use instead of G3D_PI. */ inline const double& pi() { static const double p = 3.1415926535898; return p; } + /** Returns a reference to a static double. Use instead of G3D_HALF_PI. */ inline const double& halfPi() { static const double p = 1.5707963267949; return p; } + /** Returns a reference to a static double. Use instead of G3D_TWO_PI. */ inline const double& twoPi() { static const double p = 6.283185; return p; } + /** @def G3D_PI @deprecated Use G3D::pi() instead. */ #define G3D_PI (3.1415926535898) @@ -129,12 +167,14 @@ inline const double& twoPi() { /** @def G3D_TWO_PI @deprecated Use G3D::twoPi() instead. */ #define G3D_TWO_PI (6.283185) + typedef signed char int8; typedef unsigned char uint8; typedef short int16; typedef unsigned short uint16; typedef int int32; typedef unsigned int uint32; + #ifdef _MSC_EXTENSIONS typedef __int64 int64; typedef unsigned __int64 uint64; @@ -143,25 +183,31 @@ typedef unsigned int uint32; typedef unsigned long long uint64; #endif typedef unsigned int uint; + typedef float float32; typedef double float64; + int iAbs(int iValue); int iCeil(double fValue); + /** Clamps the value to the range [low, hi] (inclusive) */ int iClamp(int val, int low, int hi); double clamp(double val, double low, double hi); float clamp(float val, float low, float hi); + /** Returns a + (b - a) * f; */ inline double lerp(double a, double b, double f) { return a + (b - a) * f; } + inline float lerp(float a, float b, float f) { return a + (b - a) * f; } + /** Wraps the value to the range [0, hi) (exclusive on the high end). This is like the clock arithmetic @@ -169,13 +215,17 @@ inline float lerp(float a, float b, float f) { to be positive. */ int iWrap(int val, int hi); + int iFloor(double fValue); + int iSign(int iValue); int iSign(double fValue); + inline int iSign(float f) { return iSign((double)f); } + /** Fast round to integer using the lrint routine. Typically 6x faster than casting to integer. @@ -183,6 +233,7 @@ inline int iSign(float f) { inline int iRound(double fValue) { return lrint(fValue); } + /** Fast round to integer using the lrint routine. Typically 6x faster than casting to integer. @@ -190,11 +241,13 @@ inline int iRound(double fValue) { inline int iRound(float f) { return lrintf(f); } + /** Returns a random number uniformly at random between low and hi (inclusive). */ int iRandom(int low, int hi); + double abs (double fValue); double aCos (double fValue); double aSin (double fValue); @@ -202,121 +255,152 @@ double aTan (double fValue); double aTan2 (double fY, double fX); double sign (double fValue); double square (double fValue); + /** Returns true if the argument is a finite real number. */ bool isFinite(double x); + /** Returns true if the argument is NaN (not a number). You can't use x == nan to test this because all comparisons against nan return false. */ bool isNaN(double x); + /** Computes x % 3. */ int iMod3(int x); + /** [0, 1] @deprecated use uniformRandom() */ double unitRandom (); + /** Uniform random number between low and hi, inclusive. @deprecated use uniformRandom() */ double random(double low, double hi); + /** [-1, 1] @deprecated use uniformRandom() */ double symmetricRandom (); + /** Uniform random number between low and hi, inclusive. [low, hi] */ float uniformRandom(float low = 0.0f, float hi = 1.0f); + /** Normally distributed random number. */ float gaussRandom(float mean = 0.0f, float stdev = 1.0f); + #if defined(_MSC_VER) && (_MSC_VER <= 1200) + /** VC6 lacks std::min and std::max */ inline double min(double x, double y) { return std::_cpp_min(x, y); } + /** VC6 lacks std::min and std::max */ inline float min(float x, float y) { return std::_cpp_min(x, y); } + /** VC6 lacks std::min and std::max */ inline int min(int x, int y) { return std::_cpp_min(x, y); } + /** VC6 lacks std::min and std::max */ inline double max(double x, double y) { return std::_cpp_max(x, y); } + /** VC6 lacks std::min and std::max */ inline float max(float x, float y) { return std::_cpp_max(x, y); } + /** VC6 lacks std::min and std::max */ inline int max(int x, int y) { return std::_cpp_max(x, y); } + #else template <class T> inline T min(const T& x, const T& y) { return std::min<T>(x, y); } + template <class T> inline T max(const T& x, const T& y) { return std::max<T>(x, y); } + #endif + int iMin(int x, int y); int iMax(int x, int y); + double square(double x); double sumSquares(double x, double y); double sumSquares(double x, double y, double z); double distance(double x, double y); double distance(double x, double y, double z); + /** Returnes the 0-based index of the highest 1 bit from the left. -1 means the number was 0. + @cite Based on code by jukka@liimatta.org */ int highestBit(uint32 x); + /** Note that fuzzyEq(a, b) && fuzzyEq(b, c) does not imply fuzzyEq(a, c), although that will be the case on some occasions. */ bool fuzzyEq(double a, double b); + /** True if a is definitely not equal to b. Guaranteed false if a == b. Possibly false when a != b.*/ bool fuzzyNe(double a, double b); + /** Is a strictly greater than b? (Guaranteed false if a <= b). (Possibly false if a > b) */ bool fuzzyGt(double a, double b); + /** Is a near or greater than b? */ bool fuzzyGe(double a, double b); + /** Is a strictly less than b? (Guaranteed false if a >= b)*/ bool fuzzyLt(double a, double b); + /** Is a near or less than b? */ bool fuzzyLe(double a, double b); + /** Computes 1 / sqrt(x). */ inline float rsq(float x) { return 1.0f / sqrtf(x); } + /** Uses SSE to implement rsq. @cite Nick nicolas@capens.net */ inline float SSErsq(float x) { + #if defined(SSE) && defined(G3D_WIN32) && !defined(_WIN64) __asm { movss xmm0, x @@ -328,38 +412,46 @@ inline float SSErsq(float x) { return 1.0f / sqrt(x); #endif } + /** Return the next power of 2 higher than the input If the input is already a power of 2, the output will be the same as the input. */ int ceilPow2(unsigned int in); + /** * True if num is a power of two. */ bool isPow2(int num); + bool isOdd(int num); bool isEven(int num); + double toRadians(double deg); double toDegrees(double rad); + /** Returns true if x is not exactly equal to 0.0f. */ inline bool any(float x) { return x != 0; } + /** Returns true if x is not exactly equal to 0.0f. */ inline bool all(float x) { return x != 0; } + /** v / v (for DirectX/Cg support) */ inline float normalize(float v) { return v / v; } + /** a * b (for DirectX/Cg support) */ @@ -367,33 +459,39 @@ inline float dot(float a, float b) { return a * b; } + /** a * b (for DirectX/Cg support) */ inline float mul(float a, float b) { return a * b; } + /** 2^x */ inline double exp2(double x) { return pow(2.0, x); } + inline double rsqrt(double x) { return 1.0 / sqrt(x); } + /** sin(x)/x */ inline double sinc(double x) { double r = sin(x) / x; + if (isNaN(r)) { return 1.0; } else { return r; } } + /** Computes a floating point modulo; the result is t wrapped to the range [lo, hi). */ @@ -401,18 +499,28 @@ inline double wrap(double t, double lo, double hi) { if ((t >= lo) && (t < hi)) { return t; } + debugAssert(hi > lo); + double interval = hi - lo; + return t - interval * iFloor((t - lo) / interval); + } + inline double wrap(double t, double hi) { return wrap(t, 0, hi); } + } // namespace + #ifdef _MSC_VER # pragma warning (pop) #endif + #include "g3dmath.inl" + #endif + diff --git a/dep/include/g3dlite/G3D/g3dmath.inl b/dep/include/g3dlite/G3D/g3dmath.inl index fa27c7e51ec..ad685bc5ce4 100644 --- a/dep/include/g3dlite/G3D/g3dmath.inl +++ b/dep/include/g3dlite/G3D/g3dmath.inl @@ -1,34 +1,45 @@ /** @file g3dmath.inl + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2001-06-02 @edited 2006-01-14 */ + #include <stdlib.h> + #ifdef _MSC_VER // Disable conditional expression is constant, which occurs incorrectly on inlined functions # pragma warning (push) # pragma warning( disable : 4127 ) #endif + namespace G3D { + inline bool isNaN(double x) { bool b1 = (x < 0.0); bool b2 = (x >= 0.0); bool b3 = !(b1 || b2); return b3; } + inline bool isFinite(double x) { return ! isNaN(x) && (x < G3D::inf()) && (x > -G3D::inf()); } + //---------------------------------------------------------------------------- inline int iAbs (int iValue) { return ( iValue >= 0 ? iValue : -iValue ); } + //---------------------------------------------------------------------------- inline int iCeil (double fValue) { return int(::ceil(fValue)); } + //---------------------------------------------------------------------------- + inline int iClamp(int val, int low, int hi) { debugAssert(low <= hi); if (val <= low) { @@ -39,7 +50,9 @@ inline int iClamp(int val, int low, int hi) { return val; } } + //---------------------------------------------------------------------------- + inline double clamp(double val, double low, double hi) { debugAssert(low <= hi); if (val <= low) { @@ -50,6 +63,7 @@ inline double clamp(double val, double low, double hi) { return val; } } + inline float clamp(float val, float low, float hi) { debugAssert(low <= hi); if (val <= low) { @@ -61,6 +75,7 @@ inline float clamp(float val, float low, float hi) { } } //---------------------------------------------------------------------------- + inline int iWrap(int val, int hi) { if (val < 0) { return ((val % hi) + hi) % hi; @@ -68,21 +83,26 @@ inline int iWrap(int val, int hi) { return val % hi; } } + //---------------------------------------------------------------------------- inline int iFloor (double fValue) { return int(::floor(fValue)); } + //---------------------------------------------------------------------------- inline int iSign (int iValue) { return ( iValue > 0 ? + 1 : ( iValue < 0 ? -1 : 0 ) ); } + inline int iSign (double fValue) { return ( fValue > 0.0 ? + 1 : ( fValue < 0.0 ? -1 : 0 ) ); } + //---------------------------------------------------------------------------- inline double abs (double fValue) { return double(::fabs(fValue)); } + //---------------------------------------------------------------------------- inline double aCos (double fValue) { if ( -1.0 < fValue ) { @@ -94,6 +114,7 @@ inline double aCos (double fValue) { return G3D_PI; } } + //---------------------------------------------------------------------------- inline double aSin (double fValue) { if ( -1.0 < fValue ) { @@ -106,90 +127,115 @@ inline double aSin (double fValue) { return G3D_HALF_PI; } } + //---------------------------------------------------------------------------- inline double aTan (double fValue) { return double(::atan(fValue)); } + //---------------------------------------------------------------------------- inline double aTan2 (double fY, double fX) { return double(::atan2(fY, fX)); } + //---------------------------------------------------------------------------- inline double sign (double fValue) { if (fValue > 0.0) { return 1.0; } + if (fValue < 0.0) { return -1.0; } + return 0.0; } + inline double G3D_DEPRECATED unitRandom () { return double(::rand()) / double(RAND_MAX); } + inline float uniformRandom(float low, float hi) { return (hi - low) * float(::rand()) / float(RAND_MAX) + low; } + //---------------------------------------------------------------------------- inline double G3D_DEPRECATED symmetricRandom () { return 2.0 * double(::rand()) / double(RAND_MAX) - 1.0; } + //---------------------------------------------------------------------------- inline double square(double x) { return x * x; } + //---------------------------------------------------------------------------- inline double sumSquares(double x, double y) { return x*x + y*y; } + //---------------------------------------------------------------------------- inline double sumSquares(double x, double y, double z) { return x*x + y*y + z*z; } + //---------------------------------------------------------------------------- inline double distance(double x, double y) { return sqrt(sumSquares(x, y)); } + //---------------------------------------------------------------------------- inline double distance(double x, double y, double z) { return sqrt(sumSquares(x, y, z)); } + //---------------------------------------------------------------------------- + /** @deprecated use G3D::min */ inline int iMin(int x, int y) { return (x >= y) ? y : x; } + //---------------------------------------------------------------------------- /** @deprecated use G3D::min */ inline int iMax(int x, int y) { return (x >= y) ? x : y; } + //---------------------------------------------------------------------------- inline int ceilPow2(unsigned int in) { in -= 1; + in |= in >> 16; in |= in >> 8; in |= in >> 4; in |= in >> 2; in |= in >> 1; + return in + 1; } + inline bool isPow2(int num) { return ((num & -num) == num); } + inline bool isOdd(int num) { return (num & 1) == 1; } + inline bool isEven(int num) { return (num & 1) == 0; } + inline double toRadians(double deg) { return deg * G3D_PI / 180.0; } + inline double toDegrees(double rad) { return rad * 180.0 / G3D_PI; } + /** Computes an appropriate epsilon for comparing a and b. */ @@ -206,28 +252,37 @@ inline double eps(double a, double b) { return fuzzyEpsilon * aa; } } + inline bool fuzzyEq(double a, double b) { return (a == b) || (abs(a - b) <= eps(a, b)); } + inline bool fuzzyNe(double a, double b) { return ! fuzzyEq(a, b); } + inline bool fuzzyGt(double a, double b) { return a > b + eps(a, b); } + inline bool fuzzyGe(double a, double b) { return a > b - eps(a, b); } + inline bool fuzzyLt(double a, double b) { return a < b - eps(a, b); } + inline bool fuzzyLe(double a, double b) { return a < b + eps(a, b); } + inline int iMod3(int x) { return x % 3; } + } // namespace G3D + #ifdef _MSC_VER // Disable conditional expression is constant, which occurs incorrectly on inlined functions # pragma warning (pop) diff --git a/dep/include/g3dlite/G3D/platform.h b/dep/include/g3dlite/G3D/platform.h index 3275a6a164c..16f9b208d18 100644 --- a/dep/include/g3dlite/G3D/platform.h +++ b/dep/include/g3dlite/G3D/platform.h @@ -1,26 +1,35 @@ /** @file platform.h + #defines for platform specific issues. + @maintainer Morgan McGuire, matrix@graphics3d.com + @created 2003-06-09 @edited 2006-01-16 */ + #ifndef G3D_PLATFORM_H #define G3D_PLATFORM_H + /** The version number of G3D in the form: MmmBB -> version M.mm [beta BB] */ #define G3D_VER 61000 + #if defined(G3D_RELEASEDEBUG) # define G3D_DEBUGRELEASE #endif + #if defined(G3D_DEBUGRELEASE) && defined(_DEBUG) # undef _DEBUG #endif + #if !defined(G3D_DEBUG) && (defined(_DEBUG) || defined(G3D_DEBUGRELEASE)) # define G3D_DEBUG #endif + #ifdef _MSC_VER #define G3D_WIN32 #elif defined(__MINGW32__) @@ -40,52 +49,65 @@ #error Unknown platform #endif + // Default to compiling with SSE, but if you want to compile // without installing SP5.0 and the Processor Pack on Windows, compile with NO_SSE // defined (can be passed to the compiler command line with /D "NO_SSE") #if !defined(NO_SSE) #define SSE #endif + #ifdef G3D_WIN32 // Turn off warnings about deprecated C routines (TODO: revisit) # pragma warning (disable : 4996) #endif + // On g++, recognize cases where the -msse2 flag was not specified #if defined(SSE) && defined(__GNUC__) && ! defined (__SSE__) # undef SSE #endif + #if defined(__GNUC__) # if __STDC_VERSION__ < 199901 # define restrict __restrict__ # endif #endif + // Verify that the supported compilers are being used and that this is a known // processor. + #ifdef G3D_LINUX # ifndef __GNUC__ # error G3D only supports the gcc compiler on Linux. # endif + //# ifndef __i386__ //# error G3D only supports x86 machines on Linux. //# endif + # define G3D_DEPRECATED __attribute__((__deprecated__)) + # ifndef __cdecl # define __cdecl __attribute__((cdecl)) # endif + # ifndef __stdcall # define __stdcall __attribute__((stdcall)) # endif + # define G3D_CHECK_PRINTF_METHOD_ARGS __attribute__((__format__(__printf__, 2, 3))) # define G3D_CHECK_VPRINTF_METHOD_ARGS __attribute__((__format__(__printf__, 2, 0))) # define G3D_CHECK_PRINTF_ARGS __attribute__((__format__(__printf__, 1, 2))) # define G3D_CHECK_VPRINTF_ARGS __attribute__((__format__(__printf__, 1, 0))) #endif + #ifdef G3D_OSX #ifndef __GNUC__ #error G3D only supports the gcc compiler on OS X. #endif + #if defined(__i386__) #define G3D_OSX_INTEL #elif defined(__PPC__) @@ -93,24 +115,30 @@ #else #define G3D_OSX_UNKNOWN #endif + # ifndef __cdecl # define __cdecl __attribute__((cdecl)) # endif + # ifndef __stdcall # define __stdcall __attribute__((stdcall)) # endif + # define G3D_DEPRECATED __attribute__((__deprecated__)) + # define G3D_CHECK_PRINTF_METHOD_ARGS __attribute__((__format__(__printf__, 2, 3))) # define G3D_CHECK_VPRINTF_METHOD_ARGS __attribute__((__format__(__printf__, 2, 0))) # define G3D_CHECK_PRINTF_ARGS __attribute__((__format__(__printf__, 1, 2))) # define G3D_CHECK_VPRINTF_ARGS __attribute__((__format__(__printf__, 1, 0))) #endif + #ifdef G3D_WIN32 // Microsoft Visual C++ 7.1 _MSC_VER = 1310 // Microsoft Visual C++ 7.0 _MSC_VER = 1300 // Microsoft Visual C++ 6.0 _MSC_VER = 1200 // Microsoft Visual C++ 5.0 _MSC_VER = 1100 + // Old versions of MSVC (6.0 and previous) don't // support C99 for loop scoping rules. This fixes them. # if (_MSC_VER <= 1200) @@ -118,34 +146,42 @@ # pragma warning (disable : 4127) # define for if (false) {} else for # endif + # if (_MSC_VER <= 1200) // Nothing we can do on VC6 for deprecated functions # define G3D_DEPRECATED # else # define G3D_DEPRECATED __declspec(deprecated) # endif + // Prevent Winsock conflicts by hiding the winsock API #ifndef _WINSOCKAPI_ # define _G3D_INTERNAL_HIDE_WINSOCK_ # define _WINSOCKAPI_ # endif + // Disable 'name too long for browse information' warning # pragma warning (disable : 4786) // TODO: remove # pragma warning (disable : 4244) + # if defined(_MSC_VER) && (_MSC_VER <= 1200) // VC6 std:: has signed problems in it # pragma warning (disable : 4018) # endif + # define ZLIB_WINAPI + // Mingw32 defines restrict # ifndef G3D_MINGW32 # define restrict # endif + # define G3D_CHECK_PRINTF_ARGS # define G3D_CHECK_VPRINTF_ARGS # define G3D_CHECK_PRINTF_METHOD_ARGS # define G3D_CHECK_VPRINTF_METHOD_ARGS + // On MSVC, we need to link against the multithreaded DLL version of // the C++ runtime because that is what SDL and ZLIB are compiled // against. This is not the default for MSVC, so we set the following @@ -155,11 +191,13 @@ // http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore/html/_core_.2f.md.2c_2f.ml.2c_2f.mt.2c_2f.ld.asp // http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/HTML/_core_Compiler_Reference.asp // + #if 0 //ignore that for Trinity // DLL runtime #ifndef _DLL #define _DLL #endif + // Multithreaded runtime #ifndef _MT #define _MT 1 @@ -169,6 +207,7 @@ #undef _STATIC_CPPLIB #endif #endif + #ifdef _DEBUG #pragma comment (linker, "/NODEFAULTLIB:libc.lib") #pragma comment (linker, "/NODEFAULTLIB:libcmt.lib") @@ -182,38 +221,50 @@ #pragma comment(linker, "/NODEFAULTLIB:libcmtd.lib") #pragma comment(linker, "/NODEFAULTLIB:msvcrtd.lib") #endif + // Now set up external linking + #ifdef _DEBUG // zlib and SDL were linked against the release MSVCRT; force // the debug version. #pragma comment(linker, "/NODEFAULTLIB:MSVCRT.LIB") # endif + # ifndef WIN32_LEAN_AND_MEAN # define WIN32_LEAN_AND_MEAN 1 # endif + # define NOMINMAX 1 # include <windows.h> # undef WIN32_LEAN_AND_MEAN # undef NOMINMAX + #ifdef _G3D_INTERNAL_HIDE_WINSOCK_ # undef _G3D_INTERNAL_HIDE_WINSOCK_ # undef _WINSOCKAPI_ #endif + #endif + # if defined(_MSC_VER) && (_MSC_VER <= 1200) // VC6 std:: has signed/unsigned problems # pragma warning (disable : 4018) # endif + /** @def STR(expression) + Creates a string from the expression. Frequently used with G3D::Shader to express shading programs inline. + <CODE>STR(this becomes a string)<PRE> evaluates the same as <CODE>"this becomes a string"</CODE> */ #define STR(x) #x + #undef G3D_DEPRECATED #define G3D_DEPRECATED + // Header guard #endif diff --git a/dep/include/g3dlite/G3D/stringutils.h b/dep/include/g3dlite/G3D/stringutils.h index eae346b0985..59449313bf5 100644 --- a/dep/include/g3dlite/G3D/stringutils.h +++ b/dep/include/g3dlite/G3D/stringutils.h @@ -1,28 +1,37 @@ /** @file stringutils.h + @maintainer Morgan McGuire, matrix@graphics3d.com + @author 2000-09-09 @edited 2002-11-30 */ + #ifndef G3D_STRINGUTILS_H #define G3D_STRINGUTILS_H + #include "G3D/platform.h" #include "G3D/Array.h" #include <string> + namespace G3D { + extern const char* NEWLINE; + /** Returns true if the test string begins with the pattern string. */ bool beginsWith( const std::string& test, const std::string& pattern); + /** Returns true if the test string ends with the pattern string. */ bool endsWith( const std::string& test, const std::string& pattern); + /** Produces a new string that is the input string wrapped at a certain number of columns (where @@ -33,28 +42,34 @@ bool endsWith( std::string wordWrap( const std::string& input, int numCols); + /** A comparison function for passing to Array::sort. */ int stringCompare( const std::string& s1, const std::string& s2); + int stringPtrCompare( const std::string* s1, const std::string* s2); + /** Returns a new string that is an uppercase version of x. */ std::string toUpper( const std::string& x); + std::string toLower( const std::string& x); + /** Splits x at each occurance of splitChar. */ G3D::Array<std::string> stringSplit( const std::string& x, char splitChar); + /** joinChar is not inserted at the beginning or end, just in between elements. @@ -62,44 +77,55 @@ G3D::Array<std::string> stringSplit( std::string stringJoin( const G3D::Array<std::string>& a, char joinChar); + std::string stringJoin( const G3D::Array<std::string>& a, const std::string& joinStr); + /** Strips whitespace from both ends of the string. */ std::string trimWhitespace( const std::string& s); + /** These standard C functions are renamed for clarity/naming conventions and to return bool, not int. */ inline bool isWhiteSpace(const char c) { return isspace(c) != 0; } + /** These standard C functions are renamed for clarity/naming conventions and to return bool, not int. */ inline bool isNewline(const char c) { return (c == '\n') || (c == '\r'); } + /** These standard C functions are renamed for clarity/naming conventions and to return bool, not int. */ inline bool isDigit(const char c) { return isdigit(c) != 0; } + /** These standard C functions are renamed for clarity/naming conventions and to return bool, not int. */ inline bool isLetter(const char c) { return isalpha(c) != 0; } + inline bool isSlash(const char c) { return (c == '\\') || (c == '/'); } + inline bool isQuote(const char c) { return (c == '\'') || (c == '\"'); } + }; // namespace + #endif + |