diff options
author | Erwin Coumans <blender@erwincoumans.com> | 2011-03-12 23:34:17 +0300 |
---|---|---|
committer | Erwin Coumans <blender@erwincoumans.com> | 2011-03-12 23:34:17 +0300 |
commit | 5e374328a87c1b418f8454d5ef38470484804961 (patch) | |
tree | 1d6de85165175c5192f74dbd423e1d5cb48f8ff6 /extern/bullet2/src/LinearMath | |
parent | 8c526e79e31d40d56a6fecce9343c74bd9fe62d8 (diff) |
update Bullet physics sdk to latest trunk/version 2.78
add PhysicsConstraints.exportBulletFile(char* fileName) python command
I'll be checking the bf-committers mailing list, in case this commit broke stuff
scons needs to be updated, I'll do that in a second.
Diffstat (limited to 'extern/bullet2/src/LinearMath')
19 files changed, 3155 insertions, 909 deletions
diff --git a/extern/bullet2/src/LinearMath/btAlignedAllocator.cpp b/extern/bullet2/src/LinearMath/btAlignedAllocator.cpp index a3d790f8abc..189b759d237 100644 --- a/extern/bullet2/src/LinearMath/btAlignedAllocator.cpp +++ b/extern/bullet2/src/LinearMath/btAlignedAllocator.cpp @@ -160,22 +160,8 @@ void btAlignedFreeInternal (void* ptr,int line,char* filename) void* btAlignedAllocInternal (size_t size, int alignment) { gNumAlignedAllocs++; - void* ptr; -#if defined (BT_HAS_ALIGNED_ALLOCATOR) || defined(__CELLOS_LV2__) + void* ptr; ptr = sAlignedAllocFunc(size, alignment); -#else - char *real; - unsigned long offset; - - real = (char *)sAllocFunc(size + sizeof(void *) + (alignment-1)); - if (real) { - offset = (alignment - (unsigned long)(real + sizeof(void *))) & (alignment-1); - ptr = (void *)((real + sizeof(void *)) + offset); - *((void **)(ptr)-1) = (void *)(real); - } else { - ptr = (void *)(real); - } -#endif // defined (BT_HAS_ALIGNED_ALLOCATOR) || defined(__CELLOS_LV2__) // printf("btAlignedAllocInternal %d, %x\n",size,ptr); return ptr; } @@ -189,16 +175,7 @@ void btAlignedFreeInternal (void* ptr) gNumAlignedFree++; // printf("btAlignedFreeInternal %x\n",ptr); -#if defined (BT_HAS_ALIGNED_ALLOCATOR) || defined(__CELLOS_LV2__) sAlignedFreeFunc(ptr); -#else - void* real; - - if (ptr) { - real = *((void **)(ptr)-1); - sFreeFunc(real); - } -#endif // defined (BT_HAS_ALIGNED_ALLOCATOR) || defined(__CELLOS_LV2__) } #endif //BT_DEBUG_MEMORY_ALLOCATIONS diff --git a/extern/bullet2/src/LinearMath/btAlignedObjectArray.h b/extern/bullet2/src/LinearMath/btAlignedObjectArray.h index bad1eee1f63..955bb128e83 100644 --- a/extern/bullet2/src/LinearMath/btAlignedObjectArray.h +++ b/extern/bullet2/src/LinearMath/btAlignedObjectArray.h @@ -138,6 +138,16 @@ class btAlignedObjectArray return m_size; } + SIMD_FORCE_INLINE const T& at(int n) const + { + return m_data[n]; + } + + SIMD_FORCE_INLINE T& at(int n) + { + return m_data[n]; + } + SIMD_FORCE_INLINE const T& operator[](int n) const { return m_data[n]; @@ -171,9 +181,9 @@ class btAlignedObjectArray { int curSize = size(); - if (newsize < size()) + if (newsize < curSize) { - for(int i = curSize; i < newsize; i++) + for(int i = newsize; i < curSize; i++) { m_data[i].~T(); } @@ -195,6 +205,18 @@ class btAlignedObjectArray m_size = newsize; } + SIMD_FORCE_INLINE T& expandNonInitializing( ) + { + int sz = size(); + if( sz == capacity() ) + { + reserve( allocSize(size()) ); + } + m_size++; + + return m_data[sz]; + } + SIMD_FORCE_INLINE T& expand( const T& fillValue=T()) { @@ -384,7 +406,7 @@ class btAlignedObjectArray int findBinarySearch(const T& key) const { int first = 0; - int last = size(); + int last = size()-1; //assume sorted array while (first <= last) { @@ -437,6 +459,13 @@ class btAlignedObjectArray m_capacity = capacity; } + void copyFromArray(const btAlignedObjectArray& otherArray) + { + int otherSize = otherArray.size(); + resize (otherSize); + otherArray.copy(0, otherSize, m_data); + } + }; #endif //BT_OBJECT_ARRAY__ diff --git a/extern/bullet2/src/LinearMath/btConvexHull.cpp b/extern/bullet2/src/LinearMath/btConvexHull.cpp index 419c752a1d9..532d76d881f 100644 --- a/extern/bullet2/src/LinearMath/btConvexHull.cpp +++ b/extern/bullet2/src/LinearMath/btConvexHull.cpp @@ -16,9 +16,9 @@ subject to the following restrictions: #include <string.h> #include "btConvexHull.h" -#include "LinearMath/btAlignedObjectArray.h" -#include "LinearMath/btMinMax.h" -#include "LinearMath/btVector3.h" +#include "btAlignedObjectArray.h" +#include "btMinMax.h" +#include "btVector3.h" @@ -96,21 +96,21 @@ btVector3 PlaneLineIntersection(const btPlane &plane, const btVector3 &p0, const // returns the point where the line p0-p1 intersects the plane n&d static btVector3 dif; dif = p1-p0; - btScalar dn= dot(plane.normal,dif); - btScalar t = -(plane.dist+dot(plane.normal,p0) )/dn; + btScalar dn= btDot(plane.normal,dif); + btScalar t = -(plane.dist+btDot(plane.normal,p0) )/dn; return p0 + (dif*t); } btVector3 PlaneProject(const btPlane &plane, const btVector3 &point) { - return point - plane.normal * (dot(point,plane.normal)+plane.dist); + return point - plane.normal * (btDot(point,plane.normal)+plane.dist); } btVector3 TriNormal(const btVector3 &v0, const btVector3 &v1, const btVector3 &v2) { // return the normal of the triangle // inscribed by v0, v1, and v2 - btVector3 cp=cross(v1-v0,v2-v1); + btVector3 cp=btCross(v1-v0,v2-v1); btScalar m=cp.length(); if(m==0) return btVector3(1,0,0); return cp*(btScalar(1.0)/m); @@ -120,23 +120,23 @@ btVector3 TriNormal(const btVector3 &v0, const btVector3 &v1, const btVector3 &v btScalar DistanceBetweenLines(const btVector3 &ustart, const btVector3 &udir, const btVector3 &vstart, const btVector3 &vdir, btVector3 *upoint, btVector3 *vpoint) { static btVector3 cp; - cp = cross(udir,vdir).normalized(); + cp = btCross(udir,vdir).normalized(); - btScalar distu = -dot(cp,ustart); - btScalar distv = -dot(cp,vstart); + btScalar distu = -btDot(cp,ustart); + btScalar distv = -btDot(cp,vstart); btScalar dist = (btScalar)fabs(distu-distv); if(upoint) { btPlane plane; - plane.normal = cross(vdir,cp).normalized(); - plane.dist = -dot(plane.normal,vstart); + plane.normal = btCross(vdir,cp).normalized(); + plane.dist = -btDot(plane.normal,vstart); *upoint = PlaneLineIntersection(plane,ustart,ustart+udir); } if(vpoint) { btPlane plane; - plane.normal = cross(udir,cp).normalized(); - plane.dist = -dot(plane.normal,ustart); + plane.normal = btCross(udir,cp).normalized(); + plane.dist = -btDot(plane.normal,ustart); *vpoint = PlaneLineIntersection(plane,vstart,vstart+vdir); } return dist; @@ -170,7 +170,7 @@ ConvexH::ConvexH(int vertices_size,int edges_size,int facets_size) int PlaneTest(const btPlane &p, const btVector3 &v); int PlaneTest(const btPlane &p, const btVector3 &v) { - btScalar a = dot(v,p.normal)+p.dist; + btScalar a = btDot(v,p.normal)+p.dist; int flag = (a>planetestepsilon)?OVER:((a<-planetestepsilon)?UNDER:COPLANAR); return flag; } @@ -228,7 +228,7 @@ int maxdirfiltered(const T *p,int count,const T &dir,btAlignedObjectArray<int> & for(int i=0;i<count;i++) if(allow[i]) { - if(m==-1 || dot(p[i],dir)>dot(p[m],dir)) + if(m==-1 || btDot(p[i],dir)>btDot(p[m],dir)) m=i; } btAssert(m!=-1); @@ -238,8 +238,8 @@ int maxdirfiltered(const T *p,int count,const T &dir,btAlignedObjectArray<int> & btVector3 orth(const btVector3 &v); btVector3 orth(const btVector3 &v) { - btVector3 a=cross(v,btVector3(0,0,1)); - btVector3 b=cross(v,btVector3(0,1,0)); + btVector3 a=btCross(v,btVector3(0,0,1)); + btVector3 b=btCross(v,btVector3(0,1,0)); if (a.length() > b.length()) { return a.normalized(); @@ -258,7 +258,7 @@ int maxdirsterid(const T *p,int count,const T &dir,btAlignedObjectArray<int> &al m = maxdirfiltered(p,count,dir,allow); if(allow[m]==3) return m; T u = orth(dir); - T v = cross(u,dir); + T v = btCross(u,dir); int ma=-1; for(btScalar x = btScalar(0.0) ; x<= btScalar(360.0) ; x+= btScalar(45.0)) { @@ -313,7 +313,7 @@ int above(btVector3* vertices,const int3& t, const btVector3 &p, btScalar epsilo int above(btVector3* vertices,const int3& t, const btVector3 &p, btScalar epsilon) { btVector3 n=TriNormal(vertices[t[0]],vertices[t[1]],vertices[t[2]]); - return (dot(n,p-vertices[t[0]]) > epsilon); // EPSILON??? + return (btDot(n,p-vertices[t[0]]) > epsilon); // EPSILON??? } int hasedge(const int3 &t, int a,int b); int hasedge(const int3 &t, int a,int b) @@ -495,8 +495,8 @@ int4 HullLibrary::FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectAr basis[0] = verts[p0]-verts[p1]; if(p0==p1 || basis[0]==btVector3(0,0,0)) return int4(-1,-1,-1,-1); - basis[1] = cross(btVector3( btScalar(1),btScalar(0.02), btScalar(0)),basis[0]); - basis[2] = cross(btVector3(btScalar(-0.02), btScalar(1), btScalar(0)),basis[0]); + basis[1] = btCross(btVector3( btScalar(1),btScalar(0.02), btScalar(0)),basis[0]); + basis[2] = btCross(btVector3(btScalar(-0.02), btScalar(1), btScalar(0)),basis[0]); if (basis[1].length() > basis[2].length()) { basis[1].normalize(); @@ -512,13 +512,13 @@ int4 HullLibrary::FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectAr if(p2 == p0 || p2 == p1) return int4(-1,-1,-1,-1); basis[1] = verts[p2] - verts[p0]; - basis[2] = cross(basis[1],basis[0]).normalized(); + basis[2] = btCross(basis[1],basis[0]).normalized(); int p3 = maxdirsterid(verts,verts_count,basis[2],allow); if(p3==p0||p3==p1||p3==p2) p3 = maxdirsterid(verts,verts_count,-basis[2],allow); if(p3==p0||p3==p1||p3==p2) return int4(-1,-1,-1,-1); btAssert(!(p0==p1||p0==p2||p0==p3||p1==p2||p1==p3||p2==p3)); - if(dot(verts[p3]-verts[p0],cross(verts[p1]-verts[p0],verts[p2]-verts[p0])) <0) {Swap(p2,p3);} + if(btDot(verts[p3]-verts[p0],btCross(verts[p1]-verts[p0],verts[p2]-verts[p0])) <0) {Swap(p2,p3);} return int4(p0,p1,p2,p3); } @@ -564,7 +564,7 @@ int HullLibrary::calchullgen(btVector3 *verts,int verts_count, int vlimit) btAssert(t->vmax<0); btVector3 n=TriNormal(verts[(*t)[0]],verts[(*t)[1]],verts[(*t)[2]]); t->vmax = maxdirsterid(verts,verts_count,n,allow); - t->rise = dot(n,verts[t->vmax]-verts[(*t)[0]]); + t->rise = btDot(n,verts[t->vmax]-verts[(*t)[0]]); } btHullTriangle *te; vlimit-=4; @@ -592,7 +592,7 @@ int HullLibrary::calchullgen(btVector3 *verts,int verts_count, int vlimit) if(!m_tris[j]) continue; if(!hasvert(*m_tris[j],v)) break; int3 nt=*m_tris[j]; - if(above(verts,nt,center,btScalar(0.01)*epsilon) || cross(verts[nt[1]]-verts[nt[0]],verts[nt[2]]-verts[nt[1]]).length()< epsilon*epsilon*btScalar(0.1) ) + if(above(verts,nt,center,btScalar(0.01)*epsilon) || btCross(verts[nt[1]]-verts[nt[0]],verts[nt[2]]-verts[nt[1]]).length()< epsilon*epsilon*btScalar(0.1) ) { btHullTriangle *nb = m_tris[m_tris[j]->n[0]]; btAssert(nb);btAssert(!hasvert(*nb,v));btAssert(nb->id<j); @@ -614,7 +614,7 @@ int HullLibrary::calchullgen(btVector3 *verts,int verts_count, int vlimit) } else { - t->rise = dot(n,verts[t->vmax]-verts[(*t)[0]]); + t->rise = btDot(n,verts[t->vmax]-verts[(*t)[0]]); } } vlimit --; @@ -876,7 +876,7 @@ bool HullLibrary::CleanupVertices(unsigned int svcount, vcount = 0; - btScalar recip[3]; + btScalar recip[3]={0.f,0.f,0.f}; if ( scale ) { @@ -1011,9 +1011,9 @@ bool HullLibrary::CleanupVertices(unsigned int svcount, btScalar y = v[1]; btScalar z = v[2]; - btScalar dx = fabsf(x - px ); - btScalar dy = fabsf(y - py ); - btScalar dz = fabsf(z - pz ); + btScalar dx = btFabs(x - px ); + btScalar dy = btFabs(y - py ); + btScalar dz = btFabs(z - pz ); if ( dx < normalepsilon && dy < normalepsilon && dz < normalepsilon ) { @@ -1135,7 +1135,7 @@ void HullLibrary::BringOutYourDead(const btVector3* verts,unsigned int vcount, b ocount = 0; - for (i=0; i<indexcount; i++) + for (i=0; i<int (indexcount); i++) { unsigned int v = indices[i]; // original array index @@ -1156,7 +1156,7 @@ void HullLibrary::BringOutYourDead(const btVector3* verts,unsigned int vcount, b for (int k=0;k<m_vertexIndexMapping.size();k++) { - if (tmpIndices[k]==v) + if (tmpIndices[k]==int(v)) m_vertexIndexMapping[k]=ocount; } diff --git a/extern/bullet2/src/LinearMath/btConvexHull.h b/extern/bullet2/src/LinearMath/btConvexHull.h index 92560bddb9c..a23fa4d550f 100644 --- a/extern/bullet2/src/LinearMath/btConvexHull.h +++ b/extern/bullet2/src/LinearMath/btConvexHull.h @@ -19,8 +19,8 @@ subject to the following restrictions: #ifndef CD_HULL_H #define CD_HULL_H -#include "LinearMath/btVector3.h" -#include "LinearMath/btAlignedObjectArray.h" +#include "btVector3.h" +#include "btAlignedObjectArray.h" typedef btAlignedObjectArray<unsigned int> TUIntArray; diff --git a/extern/bullet2/src/LinearMath/btDefaultMotionState.h b/extern/bullet2/src/LinearMath/btDefaultMotionState.h index d758f77ed81..7858a10d219 100644 --- a/extern/bullet2/src/LinearMath/btDefaultMotionState.h +++ b/extern/bullet2/src/LinearMath/btDefaultMotionState.h @@ -1,6 +1,8 @@ #ifndef DEFAULT_MOTION_STATE_H #define DEFAULT_MOTION_STATE_H +#include "btMotionState.h" + ///The btDefaultMotionState provides a common implementation to synchronize world transforms with offsets. struct btDefaultMotionState : public btMotionState { diff --git a/extern/bullet2/src/LinearMath/btHashMap.h b/extern/bullet2/src/LinearMath/btHashMap.h index f883e0e489a..e3302b5e9ff 100644 --- a/extern/bullet2/src/LinearMath/btHashMap.h +++ b/extern/bullet2/src/LinearMath/btHashMap.h @@ -3,94 +3,215 @@ #include "btAlignedObjectArray.h" +///very basic hashable string implementation, compatible with btHashMap +struct btHashString +{ + const char* m_string; + unsigned int m_hash; + + SIMD_FORCE_INLINE unsigned int getHash()const + { + return m_hash; + } + + btHashString(const char* name) + :m_string(name) + { + /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */ + static const unsigned int InitialFNV = 2166136261u; + static const unsigned int FNVMultiple = 16777619u; + + /* Fowler / Noll / Vo (FNV) Hash */ + unsigned int hash = InitialFNV; + + for(int i = 0; m_string[i]; i++) + { + hash = hash ^ (m_string[i]); /* xor the low 8 bits */ + hash = hash * FNVMultiple; /* multiply by the magic number */ + } + m_hash = hash; + } + + int portableStringCompare(const char* src, const char* dst) const + { + int ret = 0 ; + + while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) + ++src, ++dst; + + if ( ret < 0 ) + ret = -1 ; + else if ( ret > 0 ) + ret = 1 ; + + return( ret ); + } + + bool equals(const btHashString& other) const + { + return (m_string == other.m_string) || + (0==portableStringCompare(m_string,other.m_string)); + + } + +}; + const int BT_HASH_NULL=0xffffffff; -template <class Value> -class btHashKey + +class btHashInt { int m_uid; public: - - btHashKey(int uid) - :m_uid(uid) + btHashInt(int uid) :m_uid(uid) { } - int getUid() const + int getUid1() const { return m_uid; } + void setUid1(int uid) + { + m_uid = uid; + } + + bool equals(const btHashInt& other) const + { + return getUid1() == other.getUid1(); + } //to our success SIMD_FORCE_INLINE unsigned int getHash()const { int key = m_uid; // Thomas Wang's hash - key += ~(key << 15); - key ^= (key >> 10); - key += (key << 3); - key ^= (key >> 6); - key += ~(key << 11); - key ^= (key >> 16); + key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); return key; } +}; - btHashKey getKey(const Value& value) const + + +class btHashPtr +{ + + union { - return btHashKey(value.getUid()); + const void* m_pointer; + int m_hashValues[2]; + }; + +public: + + btHashPtr(const void* ptr) + :m_pointer(ptr) + { + } + + const void* getPointer() const + { + return m_pointer; + } + + bool equals(const btHashPtr& other) const + { + return getPointer() == other.getPointer(); + } + + //to our success + SIMD_FORCE_INLINE unsigned int getHash()const + { + const bool VOID_IS_8 = ((sizeof(void*)==8)); + + int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0]; + + // Thomas Wang's hash + key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); + return key; } + + }; template <class Value> class btHashKeyPtr { + int m_uid; +public: + + btHashKeyPtr(int uid) :m_uid(uid) + { + } + + int getUid1() const + { + return m_uid; + } + + bool equals(const btHashKeyPtr<Value>& other) const + { + return getUid1() == other.getUid1(); + } + + //to our success + SIMD_FORCE_INLINE unsigned int getHash()const + { + int key = m_uid; + // Thomas Wang's hash + key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); + return key; + } + + +}; + + +template <class Value> +class btHashKey +{ int m_uid; public: - btHashKeyPtr(int uid) - :m_uid(uid) + btHashKey(int uid) :m_uid(uid) { } - int getUid() const + int getUid1() const { return m_uid; } + bool equals(const btHashKey<Value>& other) const + { + return getUid1() == other.getUid1(); + } //to our success SIMD_FORCE_INLINE unsigned int getHash()const { int key = m_uid; // Thomas Wang's hash - key += ~(key << 15); - key ^= (key >> 10); - key += (key << 3); - key ^= (key >> 6); - key += ~(key << 11); - key ^= (key >> 16); + key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); return key; } - - btHashKeyPtr getKey(const Value& value) const - { - return btHashKeyPtr(value->getUid()); - } }; + ///The btHashMap template class implements a generic and lightweight hashmap. ///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp template <class Key, class Value> class btHashMap { +protected: btAlignedObjectArray<int> m_hashTable; btAlignedObjectArray<int> m_next; + btAlignedObjectArray<Value> m_valueArray; + btAlignedObjectArray<Key> m_keyArray; - - - void growTables(const Key& key) + void growTables(const Key& /*key*/) { int newCapacity = m_valueArray.capacity(); @@ -115,9 +236,10 @@ class btHashMap for(i=0;i<curHashtableSize;i++) { - const Value& value = m_valueArray[i]; + //const Value& value = m_valueArray[i]; + //const Key& key = m_keyArray[i]; - int hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1); // New hash value with new mask + int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1); // New hash value with new mask m_next[i] = m_hashTable[hashValue]; m_hashTable[hashValue] = i; } @@ -130,14 +252,20 @@ class btHashMap void insert(const Key& key, const Value& value) { int hash = key.getHash() & (m_valueArray.capacity()-1); - //don't add it if it is already there - if (find(key)) + + //replace value if the key is already there + int index = findIndex(key); + if (index != BT_HASH_NULL) { + m_valueArray[index]=value; return; } + int count = m_valueArray.size(); int oldCapacity = m_valueArray.capacity(); m_valueArray.push_back(value); + m_keyArray.push_back(key); + int newCapacity = m_valueArray.capacity(); if (oldCapacity < newCapacity) { @@ -191,12 +319,12 @@ class btHashMap if (lastPairIndex == pairIndex) { m_valueArray.pop_back(); + m_keyArray.pop_back(); return; } // Remove the last pair from the hash table. - const Value* lastValue = &m_valueArray[lastPairIndex]; - int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1); + int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1); index = m_hashTable[lastHash]; btAssert(index != BT_HASH_NULL); @@ -220,12 +348,14 @@ class btHashMap // Copy the last pair into the remove pair's spot. m_valueArray[pairIndex] = m_valueArray[lastPairIndex]; + m_keyArray[pairIndex] = m_keyArray[lastPairIndex]; // Insert the last pair into the hash table m_next[pairIndex] = m_hashTable[lastHash]; m_hashTable[lastHash] = pairIndex; m_valueArray.pop_back(); + m_keyArray.pop_back(); } @@ -276,15 +406,15 @@ class btHashMap int findIndex(const Key& key) const { - int hash = key.getHash() & (m_valueArray.capacity()-1); + unsigned int hash = key.getHash() & (m_valueArray.capacity()-1); - if (hash >= m_hashTable.size()) + if (hash >= (unsigned int)m_hashTable.size()) { return BT_HASH_NULL; } int index = m_hashTable[hash]; - while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false) + while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false) { index = m_next[index]; } @@ -296,6 +426,7 @@ class btHashMap m_hashTable.clear(); m_next.clear(); m_valueArray.clear(); + m_keyArray.clear(); } }; diff --git a/extern/bullet2/src/LinearMath/btIDebugDraw.h b/extern/bullet2/src/LinearMath/btIDebugDraw.h index e5a0061b779..48c15806a7d 100644 --- a/extern/bullet2/src/LinearMath/btIDebugDraw.h +++ b/extern/bullet2/src/LinearMath/btIDebugDraw.h @@ -1,27 +1,16 @@ /* -Copyright (c) 2005 Gino van den Bergen / Erwin Coumans http://continuousphysics.com - -Permission is hereby granted, free of charge, to any person or organization -obtaining a copy of the software and accompanying documentation covered by -this license (the "Software") to use, reproduce, display, distribute, -execute, and transmit the Software, and to prepare derivative works of the -Software, and to permit third-parties to whom the Software is furnished to -do so, all subject to the following: - -The copyright notices in the Software and this entire statement, including -the above license grant, this restriction and the following disclaimer, -must be included in all copies of the Software, in whole or in part, and -all derivative works of the Software, unless such copies or derivative -works are solely in the form of machine-executable object code generated by -a source language processor. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT -SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE -FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, -ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER -DEALINGS IN THE SOFTWARE. +Bullet Continuous Collision Detection and Physics Library +Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org + +This software is provided 'as-is', without any express or implied warranty. +In no event will the authors be held liable for any damages arising from the use of this software. +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it freely, +subject to the following restrictions: + +1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. */ @@ -35,6 +24,7 @@ DEALINGS IN THE SOFTWARE. ///The btIDebugDraw interface class allows hooking up a debug renderer to visually debug simulations. ///Typical use case: create a debug drawer object, and assign it to a btCollisionWorld or btDynamicsWorld using setDebugDrawer and call debugDrawWorld. ///A class that implements the btIDebugDraw interface has to implement the drawLine method at a minimum. +///For color arguments the X,Y,Z components refer to Red, Green and Blue each in the range [0..1] class btIDebugDraw { public: @@ -55,25 +45,54 @@ class btIDebugDraw DBG_EnableCCD = 1024, DBG_DrawConstraints = (1 << 11), DBG_DrawConstraintLimits = (1 << 12), + DBG_FastWireframe = (1<<13), DBG_MAX_DEBUG_DRAW_MODE }; virtual ~btIDebugDraw() {}; + virtual void drawLine(const btVector3& from,const btVector3& to,const btVector3& color)=0; + virtual void drawLine(const btVector3& from,const btVector3& to, const btVector3& fromColor, const btVector3& toColor) { + (void) toColor; drawLine (from, to, fromColor); } - virtual void drawBox (const btVector3& boxMin, const btVector3& boxMax, const btVector3& color, btScalar alpha) + virtual void drawSphere(btScalar radius, const btTransform& transform, const btVector3& color) { - } + btVector3 start = transform.getOrigin(); + + const btVector3 xoffs = transform.getBasis() * btVector3(radius,0,0); + const btVector3 yoffs = transform.getBasis() * btVector3(0,radius,0); + const btVector3 zoffs = transform.getBasis() * btVector3(0,0,radius); + // XY + drawLine(start-xoffs, start+yoffs, color); + drawLine(start+yoffs, start+xoffs, color); + drawLine(start+xoffs, start-yoffs, color); + drawLine(start-yoffs, start-xoffs, color); + + // XZ + drawLine(start-xoffs, start+zoffs, color); + drawLine(start+zoffs, start+xoffs, color); + drawLine(start+xoffs, start-zoffs, color); + drawLine(start-zoffs, start-xoffs, color); + + // YZ + drawLine(start-yoffs, start+zoffs, color); + drawLine(start+zoffs, start+yoffs, color); + drawLine(start+yoffs, start-zoffs, color); + drawLine(start-zoffs, start-yoffs, color); + } + virtual void drawSphere (const btVector3& p, btScalar radius, const btVector3& color) { + btTransform tr; + tr.setIdentity(); + tr.setOrigin(p); + drawSphere(radius,tr,color); } - - virtual void drawLine(const btVector3& from,const btVector3& to,const btVector3& color)=0; virtual void drawTriangle(const btVector3& v0,const btVector3& v1,const btVector3& v2,const btVector3& /*n0*/,const btVector3& /*n1*/,const btVector3& /*n2*/,const btVector3& color, btScalar alpha) { @@ -96,7 +115,7 @@ class btIDebugDraw virtual int getDebugMode() const = 0; - inline void drawAabb(const btVector3& from,const btVector3& to,const btVector3& color) + virtual void drawAabb(const btVector3& from,const btVector3& to,const btVector3& color) { btVector3 halfExtents = (to-from)* 0.5f; @@ -125,7 +144,7 @@ class btIDebugDraw edgecoord[i]*=-1.f; } } - void drawTransform(const btTransform& transform, btScalar orthoLen) + virtual void drawTransform(const btTransform& transform, btScalar orthoLen) { btVector3 start = transform.getOrigin(); drawLine(start, start+transform.getBasis() * btVector3(orthoLen, 0, 0), btVector3(0.7f,0,0)); @@ -133,7 +152,7 @@ class btIDebugDraw drawLine(start, start+transform.getBasis() * btVector3(0, 0, orthoLen), btVector3(0,0,0.7f)); } - void drawArc(const btVector3& center, const btVector3& normal, const btVector3& axis, btScalar radiusA, btScalar radiusB, btScalar minAngle, btScalar maxAngle, + virtual void drawArc(const btVector3& center, const btVector3& normal, const btVector3& axis, btScalar radiusA, btScalar radiusB, btScalar minAngle, btScalar maxAngle, const btVector3& color, bool drawSect, btScalar stepDegrees = btScalar(10.f)) { const btVector3& vx = axis; @@ -158,7 +177,7 @@ class btIDebugDraw drawLine(center, prev, color); } } - void drawSpherePatch(const btVector3& center, const btVector3& up, const btVector3& axis, btScalar radius, + virtual void drawSpherePatch(const btVector3& center, const btVector3& up, const btVector3& axis, btScalar radius, btScalar minTh, btScalar maxTh, btScalar minPs, btScalar maxPs, const btVector3& color, btScalar stepDegrees = btScalar(10.f)) { btVector3 vA[74]; @@ -260,7 +279,7 @@ class btIDebugDraw } } - void drawBox(const btVector3& bbMin, const btVector3& bbMax, const btVector3& color) + virtual void drawBox(const btVector3& bbMin, const btVector3& bbMax, const btVector3& color) { drawLine(btVector3(bbMin[0], bbMin[1], bbMin[2]), btVector3(bbMax[0], bbMin[1], bbMin[2]), color); drawLine(btVector3(bbMax[0], bbMin[1], bbMin[2]), btVector3(bbMax[0], bbMax[1], bbMin[2]), color); @@ -275,7 +294,7 @@ class btIDebugDraw drawLine(btVector3(bbMax[0], bbMax[1], bbMax[2]), btVector3(bbMin[0], bbMax[1], bbMax[2]), color); drawLine(btVector3(bbMin[0], bbMax[1], bbMax[2]), btVector3(bbMin[0], bbMin[1], bbMax[2]), color); } - void drawBox(const btVector3& bbMin, const btVector3& bbMax, const btTransform& trans, const btVector3& color) + virtual void drawBox(const btVector3& bbMin, const btVector3& bbMax, const btTransform& trans, const btVector3& color) { drawLine(trans * btVector3(bbMin[0], bbMin[1], bbMin[2]), trans * btVector3(bbMax[0], bbMin[1], bbMin[2]), color); drawLine(trans * btVector3(bbMax[0], bbMin[1], bbMin[2]), trans * btVector3(bbMax[0], bbMax[1], bbMin[2]), color); @@ -290,6 +309,107 @@ class btIDebugDraw drawLine(trans * btVector3(bbMax[0], bbMax[1], bbMax[2]), trans * btVector3(bbMin[0], bbMax[1], bbMax[2]), color); drawLine(trans * btVector3(bbMin[0], bbMax[1], bbMax[2]), trans * btVector3(bbMin[0], bbMin[1], bbMax[2]), color); } + + virtual void drawCapsule(btScalar radius, btScalar halfHeight, int upAxis, const btTransform& transform, const btVector3& color) + { + btVector3 capStart(0.f,0.f,0.f); + capStart[upAxis] = -halfHeight; + + btVector3 capEnd(0.f,0.f,0.f); + capEnd[upAxis] = halfHeight; + + // Draw the ends + { + + btTransform childTransform = transform; + childTransform.getOrigin() = transform * capStart; + drawSphere(radius, childTransform, color); + } + + { + btTransform childTransform = transform; + childTransform.getOrigin() = transform * capEnd; + drawSphere(radius, childTransform, color); + } + + // Draw some additional lines + btVector3 start = transform.getOrigin(); + + capStart[(upAxis+1)%3] = radius; + capEnd[(upAxis+1)%3] = radius; + drawLine(start+transform.getBasis() * capStart,start+transform.getBasis() * capEnd, color); + capStart[(upAxis+1)%3] = -radius; + capEnd[(upAxis+1)%3] = -radius; + drawLine(start+transform.getBasis() * capStart,start+transform.getBasis() * capEnd, color); + + capStart[(upAxis+1)%3] = 0.f; + capEnd[(upAxis+1)%3] = 0.f; + + capStart[(upAxis+2)%3] = radius; + capEnd[(upAxis+2)%3] = radius; + drawLine(start+transform.getBasis() * capStart,start+transform.getBasis() * capEnd, color); + capStart[(upAxis+2)%3] = -radius; + capEnd[(upAxis+2)%3] = -radius; + drawLine(start+transform.getBasis() * capStart,start+transform.getBasis() * capEnd, color); + } + + virtual void drawCylinder(btScalar radius, btScalar halfHeight, int upAxis, const btTransform& transform, const btVector3& color) + { + btVector3 start = transform.getOrigin(); + btVector3 offsetHeight(0,0,0); + offsetHeight[upAxis] = halfHeight; + btVector3 offsetRadius(0,0,0); + offsetRadius[(upAxis+1)%3] = radius; + drawLine(start+transform.getBasis() * (offsetHeight+offsetRadius),start+transform.getBasis() * (-offsetHeight+offsetRadius),color); + drawLine(start+transform.getBasis() * (offsetHeight-offsetRadius),start+transform.getBasis() * (-offsetHeight-offsetRadius),color); + + // Drawing top and bottom caps of the cylinder + btVector3 yaxis(0,0,0); + yaxis[upAxis] = btScalar(1.0); + btVector3 xaxis(0,0,0); + xaxis[(upAxis+1)%3] = btScalar(1.0); + drawArc(start-transform.getBasis()*(offsetHeight),transform.getBasis()*yaxis,transform.getBasis()*xaxis,radius,radius,0,SIMD_2_PI,color,false,btScalar(10.0)); + drawArc(start+transform.getBasis()*(offsetHeight),transform.getBasis()*yaxis,transform.getBasis()*xaxis,radius,radius,0,SIMD_2_PI,color,false,btScalar(10.0)); + } + + virtual void drawCone(btScalar radius, btScalar height, int upAxis, const btTransform& transform, const btVector3& color) + { + + btVector3 start = transform.getOrigin(); + + btVector3 offsetHeight(0,0,0); + offsetHeight[upAxis] = height * btScalar(0.5); + btVector3 offsetRadius(0,0,0); + offsetRadius[(upAxis+1)%3] = radius; + btVector3 offset2Radius(0,0,0); + offset2Radius[(upAxis+2)%3] = radius; + + drawLine(start+transform.getBasis() * (offsetHeight),start+transform.getBasis() * (-offsetHeight+offsetRadius),color); + drawLine(start+transform.getBasis() * (offsetHeight),start+transform.getBasis() * (-offsetHeight-offsetRadius),color); + drawLine(start+transform.getBasis() * (offsetHeight),start+transform.getBasis() * (-offsetHeight+offset2Radius),color); + drawLine(start+transform.getBasis() * (offsetHeight),start+transform.getBasis() * (-offsetHeight-offset2Radius),color); + + // Drawing the base of the cone + btVector3 yaxis(0,0,0); + yaxis[upAxis] = btScalar(1.0); + btVector3 xaxis(0,0,0); + xaxis[(upAxis+1)%3] = btScalar(1.0); + drawArc(start-transform.getBasis()*(offsetHeight),transform.getBasis()*yaxis,transform.getBasis()*xaxis,radius,radius,0,SIMD_2_PI,color,false,10.0); + } + + virtual void drawPlane(const btVector3& planeNormal, btScalar planeConst, const btTransform& transform, const btVector3& color) + { + btVector3 planeOrigin = planeNormal * planeConst; + btVector3 vec0,vec1; + btPlaneSpace1(planeNormal,vec0,vec1); + btScalar vecLen = 100.f; + btVector3 pt0 = planeOrigin + vec0*vecLen; + btVector3 pt1 = planeOrigin - vec0*vecLen; + btVector3 pt2 = planeOrigin + vec1*vecLen; + btVector3 pt3 = planeOrigin - vec1*vecLen; + drawLine(transform*pt0,transform*pt1,color); + drawLine(transform*pt2,transform*pt3,color); + } }; diff --git a/extern/bullet2/src/LinearMath/btMatrix3x3.h b/extern/bullet2/src/LinearMath/btMatrix3x3.h index e45afc3c055..d0234a04369 100644 --- a/extern/bullet2/src/LinearMath/btMatrix3x3.h +++ b/extern/bullet2/src/LinearMath/btMatrix3x3.h @@ -13,162 +13,179 @@ subject to the following restrictions: */ -#ifndef btMatrix3x3_H -#define btMatrix3x3_H - -#include "btScalar.h" +#ifndef BT_MATRIX3x3_H +#define BT_MATRIX3x3_H #include "btVector3.h" #include "btQuaternion.h" +#ifdef BT_USE_DOUBLE_PRECISION +#define btMatrix3x3Data btMatrix3x3DoubleData +#else +#define btMatrix3x3Data btMatrix3x3FloatData +#endif //BT_USE_DOUBLE_PRECISION /**@brief The btMatrix3x3 class implements a 3x3 rotation matrix, to perform linear algebra in combination with btQuaternion, btTransform and btVector3. - * Make sure to only include a pure orthogonal matrix without scaling. */ +* Make sure to only include a pure orthogonal matrix without scaling. */ class btMatrix3x3 { - public: - /** @brief No initializaion constructor */ - btMatrix3x3 () {} - -// explicit btMatrix3x3(const btScalar *m) { setFromOpenGLSubMatrix(m); } - - /**@brief Constructor from Quaternion */ - explicit btMatrix3x3(const btQuaternion& q) { setRotation(q); } - /* - template <typename btScalar> - Matrix3x3(const btScalar& yaw, const btScalar& pitch, const btScalar& roll) - { - setEulerYPR(yaw, pitch, roll); - } - */ - /** @brief Constructor with row major formatting */ - btMatrix3x3(const btScalar& xx, const btScalar& xy, const btScalar& xz, - const btScalar& yx, const btScalar& yy, const btScalar& yz, - const btScalar& zx, const btScalar& zy, const btScalar& zz) - { - setValue(xx, xy, xz, - yx, yy, yz, - zx, zy, zz); - } - /** @brief Copy constructor */ - SIMD_FORCE_INLINE btMatrix3x3 (const btMatrix3x3& other) - { - m_el[0] = other.m_el[0]; - m_el[1] = other.m_el[1]; - m_el[2] = other.m_el[2]; - } - /** @brief Assignment Operator */ - SIMD_FORCE_INLINE btMatrix3x3& operator=(const btMatrix3x3& other) - { - m_el[0] = other.m_el[0]; - m_el[1] = other.m_el[1]; - m_el[2] = other.m_el[2]; - return *this; - } - /** @brief Get a column of the matrix as a vector - * @param i Column number 0 indexed */ - SIMD_FORCE_INLINE btVector3 getColumn(int i) const - { - return btVector3(m_el[0][i],m_el[1][i],m_el[2][i]); - } - + ///Data storage for the matrix, each vector is a row of the matrix + btVector3 m_el[3]; - /** @brief Get a row of the matrix as a vector - * @param i Row number 0 indexed */ - SIMD_FORCE_INLINE const btVector3& getRow(int i) const - { - btFullAssert(0 <= i && i < 3); - return m_el[i]; - } +public: + /** @brief No initializaion constructor */ + btMatrix3x3 () {} - /** @brief Get a mutable reference to a row of the matrix as a vector - * @param i Row number 0 indexed */ - SIMD_FORCE_INLINE btVector3& operator[](int i) - { - btFullAssert(0 <= i && i < 3); - return m_el[i]; - } - - /** @brief Get a const reference to a row of the matrix as a vector - * @param i Row number 0 indexed */ - SIMD_FORCE_INLINE const btVector3& operator[](int i) const - { - btFullAssert(0 <= i && i < 3); - return m_el[i]; - } - - /** @brief Multiply by the target matrix on the right - * @param m Rotation matrix to be applied - * Equivilant to this = this * m */ - btMatrix3x3& operator*=(const btMatrix3x3& m); - - /** @brief Set from a carray of btScalars - * @param m A pointer to the beginning of an array of 9 btScalars */ + // explicit btMatrix3x3(const btScalar *m) { setFromOpenGLSubMatrix(m); } + + /**@brief Constructor from Quaternion */ + explicit btMatrix3x3(const btQuaternion& q) { setRotation(q); } + /* + template <typename btScalar> + Matrix3x3(const btScalar& yaw, const btScalar& pitch, const btScalar& roll) + { + setEulerYPR(yaw, pitch, roll); + } + */ + /** @brief Constructor with row major formatting */ + btMatrix3x3(const btScalar& xx, const btScalar& xy, const btScalar& xz, + const btScalar& yx, const btScalar& yy, const btScalar& yz, + const btScalar& zx, const btScalar& zy, const btScalar& zz) + { + setValue(xx, xy, xz, + yx, yy, yz, + zx, zy, zz); + } + /** @brief Copy constructor */ + SIMD_FORCE_INLINE btMatrix3x3 (const btMatrix3x3& other) + { + m_el[0] = other.m_el[0]; + m_el[1] = other.m_el[1]; + m_el[2] = other.m_el[2]; + } + /** @brief Assignment Operator */ + SIMD_FORCE_INLINE btMatrix3x3& operator=(const btMatrix3x3& other) + { + m_el[0] = other.m_el[0]; + m_el[1] = other.m_el[1]; + m_el[2] = other.m_el[2]; + return *this; + } + + /** @brief Get a column of the matrix as a vector + * @param i Column number 0 indexed */ + SIMD_FORCE_INLINE btVector3 getColumn(int i) const + { + return btVector3(m_el[0][i],m_el[1][i],m_el[2][i]); + } + + + /** @brief Get a row of the matrix as a vector + * @param i Row number 0 indexed */ + SIMD_FORCE_INLINE const btVector3& getRow(int i) const + { + btFullAssert(0 <= i && i < 3); + return m_el[i]; + } + + /** @brief Get a mutable reference to a row of the matrix as a vector + * @param i Row number 0 indexed */ + SIMD_FORCE_INLINE btVector3& operator[](int i) + { + btFullAssert(0 <= i && i < 3); + return m_el[i]; + } + + /** @brief Get a const reference to a row of the matrix as a vector + * @param i Row number 0 indexed */ + SIMD_FORCE_INLINE const btVector3& operator[](int i) const + { + btFullAssert(0 <= i && i < 3); + return m_el[i]; + } + + /** @brief Multiply by the target matrix on the right + * @param m Rotation matrix to be applied + * Equivilant to this = this * m */ + btMatrix3x3& operator*=(const btMatrix3x3& m); + + /** @brief Adds by the target matrix on the right + * @param m matrix to be applied + * Equivilant to this = this + m */ + btMatrix3x3& operator+=(const btMatrix3x3& m); + + /** @brief Substractss by the target matrix on the right + * @param m matrix to be applied + * Equivilant to this = this - m */ + btMatrix3x3& operator-=(const btMatrix3x3& m); + + /** @brief Set from the rotational part of a 4x4 OpenGL matrix + * @param m A pointer to the beginning of the array of scalars*/ void setFromOpenGLSubMatrix(const btScalar *m) - { - m_el[0].setValue(m[0],m[4],m[8]); - m_el[1].setValue(m[1],m[5],m[9]); - m_el[2].setValue(m[2],m[6],m[10]); + { + m_el[0].setValue(m[0],m[4],m[8]); + m_el[1].setValue(m[1],m[5],m[9]); + m_el[2].setValue(m[2],m[6],m[10]); - } - /** @brief Set the values of the matrix explicitly (row major) - * @param xx Top left - * @param xy Top Middle - * @param xz Top Right - * @param yx Middle Left - * @param yy Middle Middle - * @param yz Middle Right - * @param zx Bottom Left - * @param zy Bottom Middle - * @param zz Bottom Right*/ - void setValue(const btScalar& xx, const btScalar& xy, const btScalar& xz, - const btScalar& yx, const btScalar& yy, const btScalar& yz, - const btScalar& zx, const btScalar& zy, const btScalar& zz) - { - m_el[0].setValue(xx,xy,xz); - m_el[1].setValue(yx,yy,yz); - m_el[2].setValue(zx,zy,zz); - } + } + /** @brief Set the values of the matrix explicitly (row major) + * @param xx Top left + * @param xy Top Middle + * @param xz Top Right + * @param yx Middle Left + * @param yy Middle Middle + * @param yz Middle Right + * @param zx Bottom Left + * @param zy Bottom Middle + * @param zz Bottom Right*/ + void setValue(const btScalar& xx, const btScalar& xy, const btScalar& xz, + const btScalar& yx, const btScalar& yy, const btScalar& yz, + const btScalar& zx, const btScalar& zy, const btScalar& zz) + { + m_el[0].setValue(xx,xy,xz); + m_el[1].setValue(yx,yy,yz); + m_el[2].setValue(zx,zy,zz); + } + + /** @brief Set the matrix from a quaternion + * @param q The Quaternion to match */ + void setRotation(const btQuaternion& q) + { + btScalar d = q.length2(); + btFullAssert(d != btScalar(0.0)); + btScalar s = btScalar(2.0) / d; + btScalar xs = q.x() * s, ys = q.y() * s, zs = q.z() * s; + btScalar wx = q.w() * xs, wy = q.w() * ys, wz = q.w() * zs; + btScalar xx = q.x() * xs, xy = q.x() * ys, xz = q.x() * zs; + btScalar yy = q.y() * ys, yz = q.y() * zs, zz = q.z() * zs; + setValue(btScalar(1.0) - (yy + zz), xy - wz, xz + wy, + xy + wz, btScalar(1.0) - (xx + zz), yz - wx, + xz - wy, yz + wx, btScalar(1.0) - (xx + yy)); + } - /** @brief Set the matrix from a quaternion - * @param q The Quaternion to match */ - void setRotation(const btQuaternion& q) - { - btScalar d = q.length2(); - btFullAssert(d != btScalar(0.0)); - btScalar s = btScalar(2.0) / d; - btScalar xs = q.x() * s, ys = q.y() * s, zs = q.z() * s; - btScalar wx = q.w() * xs, wy = q.w() * ys, wz = q.w() * zs; - btScalar xx = q.x() * xs, xy = q.x() * ys, xz = q.x() * zs; - btScalar yy = q.y() * ys, yz = q.y() * zs, zz = q.z() * zs; - setValue(btScalar(1.0) - (yy + zz), xy - wz, xz + wy, - xy + wz, btScalar(1.0) - (xx + zz), yz - wx, - xz - wy, yz + wx, btScalar(1.0) - (xx + yy)); - } - - - /** @brief Set the matrix from euler angles using YPR around YXZ respectively - * @param yaw Yaw about Y axis - * @param pitch Pitch about X axis - * @param roll Roll about Z axis - */ - void setEulerYPR(const btScalar& yaw, const btScalar& pitch, const btScalar& roll) - { - setEulerZYX(roll, pitch, yaw); - } + + /** @brief Set the matrix from euler angles using YPR around YXZ respectively + * @param yaw Yaw about Y axis + * @param pitch Pitch about X axis + * @param roll Roll about Z axis + */ + void setEulerYPR(const btScalar& yaw, const btScalar& pitch, const btScalar& roll) + { + setEulerZYX(roll, pitch, yaw); + } /** @brief Set the matrix from euler angles YPR around ZYX axes - * @param eulerX Roll about X axis - * @param eulerY Pitch around Y axis - * @param eulerZ Yaw aboud Z axis - * - * These angles are used to produce a rotation matrix. The euler - * angles are applied in ZYX order. I.e a vector is first rotated - * about X then Y and then Z - **/ + * @param eulerX Roll about X axis + * @param eulerY Pitch around Y axis + * @param eulerZ Yaw aboud Z axis + * + * These angles are used to produce a rotation matrix. The euler + * angles are applied in ZYX order. I.e a vector is first rotated + * about X then Y and then Z + **/ void setEulerZYX(btScalar eulerX,btScalar eulerY,btScalar eulerZ) { - ///@todo proposed to reverse this since it's labeled zyx but takes arguments xyz and it will match all other parts of the code + ///@todo proposed to reverse this since it's labeled zyx but takes arguments xyz and it will match all other parts of the code btScalar ci ( btCos(eulerX)); btScalar cj ( btCos(eulerY)); btScalar ch ( btCos(eulerZ)); @@ -179,227 +196,233 @@ class btMatrix3x3 { btScalar cs = ci * sh; btScalar sc = si * ch; btScalar ss = si * sh; - + setValue(cj * ch, sj * sc - cs, sj * cc + ss, - cj * sh, sj * ss + cc, sj * cs - sc, - -sj, cj * si, cj * ci); + cj * sh, sj * ss + cc, sj * cs - sc, + -sj, cj * si, cj * ci); } - /**@brief Set the matrix to the identity */ - void setIdentity() - { - setValue(btScalar(1.0), btScalar(0.0), btScalar(0.0), - btScalar(0.0), btScalar(1.0), btScalar(0.0), - btScalar(0.0), btScalar(0.0), btScalar(1.0)); - } + /**@brief Set the matrix to the identity */ + void setIdentity() + { + setValue(btScalar(1.0), btScalar(0.0), btScalar(0.0), + btScalar(0.0), btScalar(1.0), btScalar(0.0), + btScalar(0.0), btScalar(0.0), btScalar(1.0)); + } + + static const btMatrix3x3& getIdentity() + { + static const btMatrix3x3 identityMatrix(btScalar(1.0), btScalar(0.0), btScalar(0.0), + btScalar(0.0), btScalar(1.0), btScalar(0.0), + btScalar(0.0), btScalar(0.0), btScalar(1.0)); + return identityMatrix; + } + + /**@brief Fill the rotational part of an OpenGL matrix and clear the shear/perspective + * @param m The array to be filled */ + void getOpenGLSubMatrix(btScalar *m) const + { + m[0] = btScalar(m_el[0].x()); + m[1] = btScalar(m_el[1].x()); + m[2] = btScalar(m_el[2].x()); + m[3] = btScalar(0.0); + m[4] = btScalar(m_el[0].y()); + m[5] = btScalar(m_el[1].y()); + m[6] = btScalar(m_el[2].y()); + m[7] = btScalar(0.0); + m[8] = btScalar(m_el[0].z()); + m[9] = btScalar(m_el[1].z()); + m[10] = btScalar(m_el[2].z()); + m[11] = btScalar(0.0); + } + + /**@brief Get the matrix represented as a quaternion + * @param q The quaternion which will be set */ + void getRotation(btQuaternion& q) const + { + btScalar trace = m_el[0].x() + m_el[1].y() + m_el[2].z(); + btScalar temp[4]; - static const btMatrix3x3& getIdentity() + if (trace > btScalar(0.0)) + { + btScalar s = btSqrt(trace + btScalar(1.0)); + temp[3]=(s * btScalar(0.5)); + s = btScalar(0.5) / s; + + temp[0]=((m_el[2].y() - m_el[1].z()) * s); + temp[1]=((m_el[0].z() - m_el[2].x()) * s); + temp[2]=((m_el[1].x() - m_el[0].y()) * s); + } + else { - static const btMatrix3x3 identityMatrix(btScalar(1.0), btScalar(0.0), btScalar(0.0), - btScalar(0.0), btScalar(1.0), btScalar(0.0), - btScalar(0.0), btScalar(0.0), btScalar(1.0)); - return identityMatrix; + int i = m_el[0].x() < m_el[1].y() ? + (m_el[1].y() < m_el[2].z() ? 2 : 1) : + (m_el[0].x() < m_el[2].z() ? 2 : 0); + int j = (i + 1) % 3; + int k = (i + 2) % 3; + + btScalar s = btSqrt(m_el[i][i] - m_el[j][j] - m_el[k][k] + btScalar(1.0)); + temp[i] = s * btScalar(0.5); + s = btScalar(0.5) / s; + + temp[3] = (m_el[k][j] - m_el[j][k]) * s; + temp[j] = (m_el[j][i] + m_el[i][j]) * s; + temp[k] = (m_el[k][i] + m_el[i][k]) * s; } + q.setValue(temp[0],temp[1],temp[2],temp[3]); + } + + /**@brief Get the matrix represented as euler angles around YXZ, roundtrip with setEulerYPR + * @param yaw Yaw around Y axis + * @param pitch Pitch around X axis + * @param roll around Z axis */ + void getEulerYPR(btScalar& yaw, btScalar& pitch, btScalar& roll) const + { + + // first use the normal calculus + yaw = btScalar(btAtan2(m_el[1].x(), m_el[0].x())); + pitch = btScalar(btAsin(-m_el[2].x())); + roll = btScalar(btAtan2(m_el[2].y(), m_el[2].z())); - /**@brief Fill the values of the matrix into a 9 element array - * @param m The array to be filled */ - void getOpenGLSubMatrix(btScalar *m) const + // on pitch = +/-HalfPI + if (btFabs(pitch)==SIMD_HALF_PI) { - m[0] = btScalar(m_el[0].x()); - m[1] = btScalar(m_el[1].x()); - m[2] = btScalar(m_el[2].x()); - m[3] = btScalar(0.0); - m[4] = btScalar(m_el[0].y()); - m[5] = btScalar(m_el[1].y()); - m[6] = btScalar(m_el[2].y()); - m[7] = btScalar(0.0); - m[8] = btScalar(m_el[0].z()); - m[9] = btScalar(m_el[1].z()); - m[10] = btScalar(m_el[2].z()); - m[11] = btScalar(0.0); + if (yaw>0) + yaw-=SIMD_PI; + else + yaw+=SIMD_PI; + + if (roll>0) + roll-=SIMD_PI; + else + roll+=SIMD_PI; } + }; - /**@brief Get the matrix represented as a quaternion - * @param q The quaternion which will be set */ - void getRotation(btQuaternion& q) const + + /**@brief Get the matrix represented as euler angles around ZYX + * @param yaw Yaw around X axis + * @param pitch Pitch around Y axis + * @param roll around X axis + * @param solution_number Which solution of two possible solutions ( 1 or 2) are possible values*/ + void getEulerZYX(btScalar& yaw, btScalar& pitch, btScalar& roll, unsigned int solution_number = 1) const + { + struct Euler { - btScalar trace = m_el[0].x() + m_el[1].y() + m_el[2].z(); - btScalar temp[4]; - - if (trace > btScalar(0.0)) + btScalar yaw; + btScalar pitch; + btScalar roll; + }; + + Euler euler_out; + Euler euler_out2; //second solution + //get the pointer to the raw data + + // Check that pitch is not at a singularity + if (btFabs(m_el[2].x()) >= 1) + { + euler_out.yaw = 0; + euler_out2.yaw = 0; + + // From difference of angles formula + btScalar delta = btAtan2(m_el[0].x(),m_el[0].z()); + if (m_el[2].x() > 0) //gimbal locked up { - btScalar s = btSqrt(trace + btScalar(1.0)); - temp[3]=(s * btScalar(0.5)); - s = btScalar(0.5) / s; - - temp[0]=((m_el[2].y() - m_el[1].z()) * s); - temp[1]=((m_el[0].z() - m_el[2].x()) * s); - temp[2]=((m_el[1].x() - m_el[0].y()) * s); - } - else + euler_out.pitch = SIMD_PI / btScalar(2.0); + euler_out2.pitch = SIMD_PI / btScalar(2.0); + euler_out.roll = euler_out.pitch + delta; + euler_out2.roll = euler_out.pitch + delta; + } + else // gimbal locked down { - int i = m_el[0].x() < m_el[1].y() ? - (m_el[1].y() < m_el[2].z() ? 2 : 1) : - (m_el[0].x() < m_el[2].z() ? 2 : 0); - int j = (i + 1) % 3; - int k = (i + 2) % 3; - - btScalar s = btSqrt(m_el[i][i] - m_el[j][j] - m_el[k][k] + btScalar(1.0)); - temp[i] = s * btScalar(0.5); - s = btScalar(0.5) / s; - - temp[3] = (m_el[k][j] - m_el[j][k]) * s; - temp[j] = (m_el[j][i] + m_el[i][j]) * s; - temp[k] = (m_el[k][i] + m_el[i][k]) * s; + euler_out.pitch = -SIMD_PI / btScalar(2.0); + euler_out2.pitch = -SIMD_PI / btScalar(2.0); + euler_out.roll = -euler_out.pitch + delta; + euler_out2.roll = -euler_out.pitch + delta; } - q.setValue(temp[0],temp[1],temp[2],temp[3]); } - - /**@brief Get the matrix represented as euler angles around YXZ, roundtrip with setEulerYPR - * @param yaw Yaw around Y axis - * @param pitch Pitch around X axis - * @param roll around Z axis */ - void getEulerYPR(btScalar& yaw, btScalar& pitch, btScalar& roll) const + else { - - // first use the normal calculus - yaw = btScalar(btAtan2(m_el[1].x(), m_el[0].x())); - pitch = btScalar(btAsin(-m_el[2].x())); - roll = btScalar(btAtan2(m_el[2].y(), m_el[2].z())); - - // on pitch = +/-HalfPI - if (btFabs(pitch)==SIMD_HALF_PI) - { - if (yaw>0) - yaw-=SIMD_PI; - else - yaw+=SIMD_PI; - - if (roll>0) - roll-=SIMD_PI; - else - roll+=SIMD_PI; - } - }; - + euler_out.pitch = - btAsin(m_el[2].x()); + euler_out2.pitch = SIMD_PI - euler_out.pitch; - /**@brief Get the matrix represented as euler angles around ZYX - * @param yaw Yaw around X axis - * @param pitch Pitch around Y axis - * @param roll around X axis - * @param solution_number Which solution of two possible solutions ( 1 or 2) are possible values*/ - void getEulerZYX(btScalar& yaw, btScalar& pitch, btScalar& roll, unsigned int solution_number = 1) const - { - struct Euler{btScalar yaw, pitch, roll;}; - Euler euler_out; - Euler euler_out2; //second solution - //get the pointer to the raw data - - // Check that pitch is not at a singularity - if (btFabs(m_el[2].x()) >= 1) - { - euler_out.yaw = 0; - euler_out2.yaw = 0; - - // From difference of angles formula - btScalar delta = btAtan2(m_el[0].x(),m_el[0].z()); - if (m_el[2].x() > 0) //gimbal locked up - { - euler_out.pitch = SIMD_PI / btScalar(2.0); - euler_out2.pitch = SIMD_PI / btScalar(2.0); - euler_out.roll = euler_out.pitch + delta; - euler_out2.roll = euler_out.pitch + delta; - } - else // gimbal locked down - { - euler_out.pitch = -SIMD_PI / btScalar(2.0); - euler_out2.pitch = -SIMD_PI / btScalar(2.0); - euler_out.roll = -euler_out.pitch + delta; - euler_out2.roll = -euler_out.pitch + delta; - } - } - else - { - euler_out.pitch = - btAsin(m_el[2].x()); - euler_out2.pitch = SIMD_PI - euler_out.pitch; - - euler_out.roll = btAtan2(m_el[2].y()/btCos(euler_out.pitch), - m_el[2].z()/btCos(euler_out.pitch)); - euler_out2.roll = btAtan2(m_el[2].y()/btCos(euler_out2.pitch), + euler_out.roll = btAtan2(m_el[2].y()/btCos(euler_out.pitch), + m_el[2].z()/btCos(euler_out.pitch)); + euler_out2.roll = btAtan2(m_el[2].y()/btCos(euler_out2.pitch), m_el[2].z()/btCos(euler_out2.pitch)); - - euler_out.yaw = btAtan2(m_el[1].x()/btCos(euler_out.pitch), - m_el[0].x()/btCos(euler_out.pitch)); - euler_out2.yaw = btAtan2(m_el[1].x()/btCos(euler_out2.pitch), - m_el[0].x()/btCos(euler_out2.pitch)); - } - - if (solution_number == 1) - { - yaw = euler_out.yaw; - pitch = euler_out.pitch; - roll = euler_out.roll; - } - else - { - yaw = euler_out2.yaw; - pitch = euler_out2.pitch; - roll = euler_out2.roll; - } - } - - /**@brief Create a scaled copy of the matrix - * @param s Scaling vector The elements of the vector will scale each column */ - - btMatrix3x3 scaled(const btVector3& s) const - { - return btMatrix3x3(m_el[0].x() * s.x(), m_el[0].y() * s.y(), m_el[0].z() * s.z(), - m_el[1].x() * s.x(), m_el[1].y() * s.y(), m_el[1].z() * s.z(), - m_el[2].x() * s.x(), m_el[2].y() * s.y(), m_el[2].z() * s.z()); - } - /**@brief Return the determinant of the matrix */ - btScalar determinant() const; - /**@brief Return the adjoint of the matrix */ - btMatrix3x3 adjoint() const; - /**@brief Return the matrix with all values non negative */ - btMatrix3x3 absolute() const; - /**@brief Return the transpose of the matrix */ - btMatrix3x3 transpose() const; - /**@brief Return the inverse of the matrix */ - btMatrix3x3 inverse() const; - - btMatrix3x3 transposeTimes(const btMatrix3x3& m) const; - btMatrix3x3 timesTranspose(const btMatrix3x3& m) const; - - SIMD_FORCE_INLINE btScalar tdotx(const btVector3& v) const - { - return m_el[0].x() * v.x() + m_el[1].x() * v.y() + m_el[2].x() * v.z(); + euler_out.yaw = btAtan2(m_el[1].x()/btCos(euler_out.pitch), + m_el[0].x()/btCos(euler_out.pitch)); + euler_out2.yaw = btAtan2(m_el[1].x()/btCos(euler_out2.pitch), + m_el[0].x()/btCos(euler_out2.pitch)); } - SIMD_FORCE_INLINE btScalar tdoty(const btVector3& v) const - { - return m_el[0].y() * v.x() + m_el[1].y() * v.y() + m_el[2].y() * v.z(); + + if (solution_number == 1) + { + yaw = euler_out.yaw; + pitch = euler_out.pitch; + roll = euler_out.roll; } - SIMD_FORCE_INLINE btScalar tdotz(const btVector3& v) const - { - return m_el[0].z() * v.x() + m_el[1].z() * v.y() + m_el[2].z() * v.z(); + else + { + yaw = euler_out2.yaw; + pitch = euler_out2.pitch; + roll = euler_out2.roll; } - - - /**@brief diagonalizes this matrix by the Jacobi method. - * @param rot stores the rotation from the coordinate system in which the matrix is diagonal to the original - * coordinate system, i.e., old_this = rot * new_this * rot^T. - * @param threshold See iteration - * @param iteration The iteration stops when all off-diagonal elements are less than the threshold multiplied - * by the sum of the absolute values of the diagonal, or when maxSteps have been executed. - * - * Note that this matrix is assumed to be symmetric. - */ - void diagonalize(btMatrix3x3& rot, btScalar threshold, int maxSteps) + } + + /**@brief Create a scaled copy of the matrix + * @param s Scaling vector The elements of the vector will scale each column */ + + btMatrix3x3 scaled(const btVector3& s) const + { + return btMatrix3x3(m_el[0].x() * s.x(), m_el[0].y() * s.y(), m_el[0].z() * s.z(), + m_el[1].x() * s.x(), m_el[1].y() * s.y(), m_el[1].z() * s.z(), + m_el[2].x() * s.x(), m_el[2].y() * s.y(), m_el[2].z() * s.z()); + } + + /**@brief Return the determinant of the matrix */ + btScalar determinant() const; + /**@brief Return the adjoint of the matrix */ + btMatrix3x3 adjoint() const; + /**@brief Return the matrix with all values non negative */ + btMatrix3x3 absolute() const; + /**@brief Return the transpose of the matrix */ + btMatrix3x3 transpose() const; + /**@brief Return the inverse of the matrix */ + btMatrix3x3 inverse() const; + + btMatrix3x3 transposeTimes(const btMatrix3x3& m) const; + btMatrix3x3 timesTranspose(const btMatrix3x3& m) const; + + SIMD_FORCE_INLINE btScalar tdotx(const btVector3& v) const + { + return m_el[0].x() * v.x() + m_el[1].x() * v.y() + m_el[2].x() * v.z(); + } + SIMD_FORCE_INLINE btScalar tdoty(const btVector3& v) const + { + return m_el[0].y() * v.x() + m_el[1].y() * v.y() + m_el[2].y() * v.z(); + } + SIMD_FORCE_INLINE btScalar tdotz(const btVector3& v) const + { + return m_el[0].z() * v.x() + m_el[1].z() * v.y() + m_el[2].z() * v.z(); + } + + + /**@brief diagonalizes this matrix by the Jacobi method. + * @param rot stores the rotation from the coordinate system in which the matrix is diagonal to the original + * coordinate system, i.e., old_this = rot * new_this * rot^T. + * @param threshold See iteration + * @param iteration The iteration stops when all off-diagonal elements are less than the threshold multiplied + * by the sum of the absolute values of the diagonal, or when maxSteps have been executed. + * + * Note that this matrix is assumed to be symmetric. + */ + void diagonalize(btMatrix3x3& rot, btScalar threshold, int maxSteps) + { + rot.setIdentity(); + for (int step = maxSteps; step > 0; step--) { - rot.setIdentity(); - for (int step = maxSteps; step > 0; step--) - { // find off-diagonal element [p][q] with largest magnitude int p = 0; int q = 1; @@ -408,27 +431,27 @@ class btMatrix3x3 { btScalar v = btFabs(m_el[0][2]); if (v > max) { - q = 2; - r = 1; - max = v; + q = 2; + r = 1; + max = v; } v = btFabs(m_el[1][2]); if (v > max) { - p = 1; - q = 2; - r = 0; - max = v; + p = 1; + q = 2; + r = 0; + max = v; } btScalar t = threshold * (btFabs(m_el[0][0]) + btFabs(m_el[1][1]) + btFabs(m_el[2][2])); if (max <= t) { - if (max <= SIMD_EPSILON * t) - { - return; - } - step = 1; + if (max <= SIMD_EPSILON * t) + { + return; + } + step = 1; } // compute Jacobi rotation J which leads to a zero for element [p][q] @@ -439,17 +462,17 @@ class btMatrix3x3 { btScalar sin; if (theta2 * theta2 < btScalar(10 / SIMD_EPSILON)) { - t = (theta >= 0) ? 1 / (theta + btSqrt(1 + theta2)) - : 1 / (theta - btSqrt(1 + theta2)); - cos = 1 / btSqrt(1 + t * t); - sin = cos * t; + t = (theta >= 0) ? 1 / (theta + btSqrt(1 + theta2)) + : 1 / (theta - btSqrt(1 + theta2)); + cos = 1 / btSqrt(1 + t * t); + sin = cos * t; } else { - // approximation for large theta-value, i.e., a nearly diagonal matrix - t = 1 / (theta * (2 + btScalar(0.5) / theta2)); - cos = 1 - btScalar(0.5) * t * t; - sin = cos * t; + // approximation for large theta-value, i.e., a nearly diagonal matrix + t = 1 / (theta * (2 + btScalar(0.5) / theta2)); + cos = 1 - btScalar(0.5) * t * t; + sin = cos * t; } // apply rotation to matrix (this = J^T * this * J) @@ -464,155 +487,285 @@ class btMatrix3x3 { // apply rotation to rot (rot = rot * J) for (int i = 0; i < 3; i++) { - btVector3& row = rot[i]; - mrp = row[p]; - mrq = row[q]; - row[p] = cos * mrp - sin * mrq; - row[q] = cos * mrq + sin * mrp; + btVector3& row = rot[i]; + mrp = row[p]; + mrq = row[q]; + row[p] = cos * mrp - sin * mrq; + row[q] = cos * mrq + sin * mrp; } - } } + } - - protected: - /**@brief Calculate the matrix cofactor - * @param r1 The first row to use for calculating the cofactor - * @param c1 The first column to use for calculating the cofactor - * @param r1 The second row to use for calculating the cofactor - * @param c1 The second column to use for calculating the cofactor - * See http://en.wikipedia.org/wiki/Cofactor_(linear_algebra) for more details - */ - btScalar cofac(int r1, int c1, int r2, int c2) const - { - return m_el[r1][c1] * m_el[r2][c2] - m_el[r1][c2] * m_el[r2][c1]; - } - ///Data storage for the matrix, each vector is a row of the matrix - btVector3 m_el[3]; - }; - - SIMD_FORCE_INLINE btMatrix3x3& - btMatrix3x3::operator*=(const btMatrix3x3& m) - { - setValue(m.tdotx(m_el[0]), m.tdoty(m_el[0]), m.tdotz(m_el[0]), - m.tdotx(m_el[1]), m.tdoty(m_el[1]), m.tdotz(m_el[1]), - m.tdotx(m_el[2]), m.tdoty(m_el[2]), m.tdotz(m_el[2])); - return *this; - } - - SIMD_FORCE_INLINE btScalar - btMatrix3x3::determinant() const - { - return triple((*this)[0], (*this)[1], (*this)[2]); - } - - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::absolute() const - { - return btMatrix3x3( - btFabs(m_el[0].x()), btFabs(m_el[0].y()), btFabs(m_el[0].z()), - btFabs(m_el[1].x()), btFabs(m_el[1].y()), btFabs(m_el[1].z()), - btFabs(m_el[2].x()), btFabs(m_el[2].y()), btFabs(m_el[2].z())); - } - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::transpose() const + /**@brief Calculate the matrix cofactor + * @param r1 The first row to use for calculating the cofactor + * @param c1 The first column to use for calculating the cofactor + * @param r1 The second row to use for calculating the cofactor + * @param c1 The second column to use for calculating the cofactor + * See http://en.wikipedia.org/wiki/Cofactor_(linear_algebra) for more details + */ + btScalar cofac(int r1, int c1, int r2, int c2) const { - return btMatrix3x3(m_el[0].x(), m_el[1].x(), m_el[2].x(), - m_el[0].y(), m_el[1].y(), m_el[2].y(), - m_el[0].z(), m_el[1].z(), m_el[2].z()); - } - - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::adjoint() const - { - return btMatrix3x3(cofac(1, 1, 2, 2), cofac(0, 2, 2, 1), cofac(0, 1, 1, 2), - cofac(1, 2, 2, 0), cofac(0, 0, 2, 2), cofac(0, 2, 1, 0), - cofac(1, 0, 2, 1), cofac(0, 1, 2, 0), cofac(0, 0, 1, 1)); - } - - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::inverse() const - { - btVector3 co(cofac(1, 1, 2, 2), cofac(1, 2, 2, 0), cofac(1, 0, 2, 1)); - btScalar det = (*this)[0].dot(co); - btFullAssert(det != btScalar(0.0)); - btScalar s = btScalar(1.0) / det; - return btMatrix3x3(co.x() * s, cofac(0, 2, 2, 1) * s, cofac(0, 1, 1, 2) * s, - co.y() * s, cofac(0, 0, 2, 2) * s, cofac(0, 2, 1, 0) * s, - co.z() * s, cofac(0, 1, 2, 0) * s, cofac(0, 0, 1, 1) * s); - } - - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::transposeTimes(const btMatrix3x3& m) const - { - return btMatrix3x3( - m_el[0].x() * m[0].x() + m_el[1].x() * m[1].x() + m_el[2].x() * m[2].x(), - m_el[0].x() * m[0].y() + m_el[1].x() * m[1].y() + m_el[2].x() * m[2].y(), - m_el[0].x() * m[0].z() + m_el[1].x() * m[1].z() + m_el[2].x() * m[2].z(), - m_el[0].y() * m[0].x() + m_el[1].y() * m[1].x() + m_el[2].y() * m[2].x(), - m_el[0].y() * m[0].y() + m_el[1].y() * m[1].y() + m_el[2].y() * m[2].y(), - m_el[0].y() * m[0].z() + m_el[1].y() * m[1].z() + m_el[2].y() * m[2].z(), - m_el[0].z() * m[0].x() + m_el[1].z() * m[1].x() + m_el[2].z() * m[2].x(), - m_el[0].z() * m[0].y() + m_el[1].z() * m[1].y() + m_el[2].z() * m[2].y(), - m_el[0].z() * m[0].z() + m_el[1].z() * m[1].z() + m_el[2].z() * m[2].z()); - } - - SIMD_FORCE_INLINE btMatrix3x3 - btMatrix3x3::timesTranspose(const btMatrix3x3& m) const - { - return btMatrix3x3( - m_el[0].dot(m[0]), m_el[0].dot(m[1]), m_el[0].dot(m[2]), - m_el[1].dot(m[0]), m_el[1].dot(m[1]), m_el[1].dot(m[2]), - m_el[2].dot(m[0]), m_el[2].dot(m[1]), m_el[2].dot(m[2])); - + return m_el[r1][c1] * m_el[r2][c2] - m_el[r1][c2] * m_el[r2][c1]; } - SIMD_FORCE_INLINE btVector3 - operator*(const btMatrix3x3& m, const btVector3& v) - { - return btVector3(m[0].dot(v), m[1].dot(v), m[2].dot(v)); - } - + void serialize(struct btMatrix3x3Data& dataOut) const; - SIMD_FORCE_INLINE btVector3 - operator*(const btVector3& v, const btMatrix3x3& m) - { - return btVector3(m.tdotx(v), m.tdoty(v), m.tdotz(v)); - } + void serializeFloat(struct btMatrix3x3FloatData& dataOut) const; - SIMD_FORCE_INLINE btMatrix3x3 - operator*(const btMatrix3x3& m1, const btMatrix3x3& m2) - { - return btMatrix3x3( - m2.tdotx( m1[0]), m2.tdoty( m1[0]), m2.tdotz( m1[0]), - m2.tdotx( m1[1]), m2.tdoty( m1[1]), m2.tdotz( m1[1]), - m2.tdotx( m1[2]), m2.tdoty( m1[2]), m2.tdotz( m1[2])); - } + void deSerialize(const struct btMatrix3x3Data& dataIn); + + void deSerializeFloat(const struct btMatrix3x3FloatData& dataIn); + + void deSerializeDouble(const struct btMatrix3x3DoubleData& dataIn); + +}; + + +SIMD_FORCE_INLINE btMatrix3x3& +btMatrix3x3::operator*=(const btMatrix3x3& m) +{ + setValue(m.tdotx(m_el[0]), m.tdoty(m_el[0]), m.tdotz(m_el[0]), + m.tdotx(m_el[1]), m.tdoty(m_el[1]), m.tdotz(m_el[1]), + m.tdotx(m_el[2]), m.tdoty(m_el[2]), m.tdotz(m_el[2])); + return *this; +} + +SIMD_FORCE_INLINE btMatrix3x3& +btMatrix3x3::operator+=(const btMatrix3x3& m) +{ + setValue( + m_el[0][0]+m.m_el[0][0], + m_el[0][1]+m.m_el[0][1], + m_el[0][2]+m.m_el[0][2], + m_el[1][0]+m.m_el[1][0], + m_el[1][1]+m.m_el[1][1], + m_el[1][2]+m.m_el[1][2], + m_el[2][0]+m.m_el[2][0], + m_el[2][1]+m.m_el[2][1], + m_el[2][2]+m.m_el[2][2]); + return *this; +} + +SIMD_FORCE_INLINE btMatrix3x3 +operator*(const btMatrix3x3& m, const btScalar & k) +{ + return btMatrix3x3( + m[0].x()*k,m[0].y()*k,m[0].z()*k, + m[1].x()*k,m[1].y()*k,m[1].z()*k, + m[2].x()*k,m[2].y()*k,m[2].z()*k); +} + + SIMD_FORCE_INLINE btMatrix3x3 +operator+(const btMatrix3x3& m1, const btMatrix3x3& m2) +{ + return btMatrix3x3( + m1[0][0]+m2[0][0], + m1[0][1]+m2[0][1], + m1[0][2]+m2[0][2], + m1[1][0]+m2[1][0], + m1[1][1]+m2[1][1], + m1[1][2]+m2[1][2], + m1[2][0]+m2[2][0], + m1[2][1]+m2[2][1], + m1[2][2]+m2[2][2]); +} + +SIMD_FORCE_INLINE btMatrix3x3 +operator-(const btMatrix3x3& m1, const btMatrix3x3& m2) +{ + return btMatrix3x3( + m1[0][0]-m2[0][0], + m1[0][1]-m2[0][1], + m1[0][2]-m2[0][2], + m1[1][0]-m2[1][0], + m1[1][1]-m2[1][1], + m1[1][2]-m2[1][2], + m1[2][0]-m2[2][0], + m1[2][1]-m2[2][1], + m1[2][2]-m2[2][2]); +} + + +SIMD_FORCE_INLINE btMatrix3x3& +btMatrix3x3::operator-=(const btMatrix3x3& m) +{ + setValue( + m_el[0][0]-m.m_el[0][0], + m_el[0][1]-m.m_el[0][1], + m_el[0][2]-m.m_el[0][2], + m_el[1][0]-m.m_el[1][0], + m_el[1][1]-m.m_el[1][1], + m_el[1][2]-m.m_el[1][2], + m_el[2][0]-m.m_el[2][0], + m_el[2][1]-m.m_el[2][1], + m_el[2][2]-m.m_el[2][2]); + return *this; +} + + +SIMD_FORCE_INLINE btScalar +btMatrix3x3::determinant() const +{ + return btTriple((*this)[0], (*this)[1], (*this)[2]); +} + + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::absolute() const +{ + return btMatrix3x3( + btFabs(m_el[0].x()), btFabs(m_el[0].y()), btFabs(m_el[0].z()), + btFabs(m_el[1].x()), btFabs(m_el[1].y()), btFabs(m_el[1].z()), + btFabs(m_el[2].x()), btFabs(m_el[2].y()), btFabs(m_el[2].z())); +} + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::transpose() const +{ + return btMatrix3x3(m_el[0].x(), m_el[1].x(), m_el[2].x(), + m_el[0].y(), m_el[1].y(), m_el[2].y(), + m_el[0].z(), m_el[1].z(), m_el[2].z()); +} + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::adjoint() const +{ + return btMatrix3x3(cofac(1, 1, 2, 2), cofac(0, 2, 2, 1), cofac(0, 1, 1, 2), + cofac(1, 2, 2, 0), cofac(0, 0, 2, 2), cofac(0, 2, 1, 0), + cofac(1, 0, 2, 1), cofac(0, 1, 2, 0), cofac(0, 0, 1, 1)); +} + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::inverse() const +{ + btVector3 co(cofac(1, 1, 2, 2), cofac(1, 2, 2, 0), cofac(1, 0, 2, 1)); + btScalar det = (*this)[0].dot(co); + btFullAssert(det != btScalar(0.0)); + btScalar s = btScalar(1.0) / det; + return btMatrix3x3(co.x() * s, cofac(0, 2, 2, 1) * s, cofac(0, 1, 1, 2) * s, + co.y() * s, cofac(0, 0, 2, 2) * s, cofac(0, 2, 1, 0) * s, + co.z() * s, cofac(0, 1, 2, 0) * s, cofac(0, 0, 1, 1) * s); +} + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::transposeTimes(const btMatrix3x3& m) const +{ + return btMatrix3x3( + m_el[0].x() * m[0].x() + m_el[1].x() * m[1].x() + m_el[2].x() * m[2].x(), + m_el[0].x() * m[0].y() + m_el[1].x() * m[1].y() + m_el[2].x() * m[2].y(), + m_el[0].x() * m[0].z() + m_el[1].x() * m[1].z() + m_el[2].x() * m[2].z(), + m_el[0].y() * m[0].x() + m_el[1].y() * m[1].x() + m_el[2].y() * m[2].x(), + m_el[0].y() * m[0].y() + m_el[1].y() * m[1].y() + m_el[2].y() * m[2].y(), + m_el[0].y() * m[0].z() + m_el[1].y() * m[1].z() + m_el[2].y() * m[2].z(), + m_el[0].z() * m[0].x() + m_el[1].z() * m[1].x() + m_el[2].z() * m[2].x(), + m_el[0].z() * m[0].y() + m_el[1].z() * m[1].y() + m_el[2].z() * m[2].y(), + m_el[0].z() * m[0].z() + m_el[1].z() * m[1].z() + m_el[2].z() * m[2].z()); +} + +SIMD_FORCE_INLINE btMatrix3x3 +btMatrix3x3::timesTranspose(const btMatrix3x3& m) const +{ + return btMatrix3x3( + m_el[0].dot(m[0]), m_el[0].dot(m[1]), m_el[0].dot(m[2]), + m_el[1].dot(m[0]), m_el[1].dot(m[1]), m_el[1].dot(m[2]), + m_el[2].dot(m[0]), m_el[2].dot(m[1]), m_el[2].dot(m[2])); + +} + +SIMD_FORCE_INLINE btVector3 +operator*(const btMatrix3x3& m, const btVector3& v) +{ + return btVector3(m[0].dot(v), m[1].dot(v), m[2].dot(v)); +} + + +SIMD_FORCE_INLINE btVector3 +operator*(const btVector3& v, const btMatrix3x3& m) +{ + return btVector3(m.tdotx(v), m.tdoty(v), m.tdotz(v)); +} + +SIMD_FORCE_INLINE btMatrix3x3 +operator*(const btMatrix3x3& m1, const btMatrix3x3& m2) +{ + return btMatrix3x3( + m2.tdotx( m1[0]), m2.tdoty( m1[0]), m2.tdotz( m1[0]), + m2.tdotx( m1[1]), m2.tdoty( m1[1]), m2.tdotz( m1[1]), + m2.tdotx( m1[2]), m2.tdoty( m1[2]), m2.tdotz( m1[2])); +} /* - SIMD_FORCE_INLINE btMatrix3x3 btMultTransposeLeft(const btMatrix3x3& m1, const btMatrix3x3& m2) { - return btMatrix3x3( - m1[0][0] * m2[0][0] + m1[1][0] * m2[1][0] + m1[2][0] * m2[2][0], - m1[0][0] * m2[0][1] + m1[1][0] * m2[1][1] + m1[2][0] * m2[2][1], - m1[0][0] * m2[0][2] + m1[1][0] * m2[1][2] + m1[2][0] * m2[2][2], - m1[0][1] * m2[0][0] + m1[1][1] * m2[1][0] + m1[2][1] * m2[2][0], - m1[0][1] * m2[0][1] + m1[1][1] * m2[1][1] + m1[2][1] * m2[2][1], - m1[0][1] * m2[0][2] + m1[1][1] * m2[1][2] + m1[2][1] * m2[2][2], - m1[0][2] * m2[0][0] + m1[1][2] * m2[1][0] + m1[2][2] * m2[2][0], - m1[0][2] * m2[0][1] + m1[1][2] * m2[1][1] + m1[2][2] * m2[2][1], - m1[0][2] * m2[0][2] + m1[1][2] * m2[1][2] + m1[2][2] * m2[2][2]); +SIMD_FORCE_INLINE btMatrix3x3 btMultTransposeLeft(const btMatrix3x3& m1, const btMatrix3x3& m2) { +return btMatrix3x3( +m1[0][0] * m2[0][0] + m1[1][0] * m2[1][0] + m1[2][0] * m2[2][0], +m1[0][0] * m2[0][1] + m1[1][0] * m2[1][1] + m1[2][0] * m2[2][1], +m1[0][0] * m2[0][2] + m1[1][0] * m2[1][2] + m1[2][0] * m2[2][2], +m1[0][1] * m2[0][0] + m1[1][1] * m2[1][0] + m1[2][1] * m2[2][0], +m1[0][1] * m2[0][1] + m1[1][1] * m2[1][1] + m1[2][1] * m2[2][1], +m1[0][1] * m2[0][2] + m1[1][1] * m2[1][2] + m1[2][1] * m2[2][2], +m1[0][2] * m2[0][0] + m1[1][2] * m2[1][0] + m1[2][2] * m2[2][0], +m1[0][2] * m2[0][1] + m1[1][2] * m2[1][1] + m1[2][2] * m2[2][1], +m1[0][2] * m2[0][2] + m1[1][2] * m2[1][2] + m1[2][2] * m2[2][2]); } */ /**@brief Equality operator between two matrices - * It will test all elements are equal. */ +* It will test all elements are equal. */ SIMD_FORCE_INLINE bool operator==(const btMatrix3x3& m1, const btMatrix3x3& m2) { - return ( m1[0][0] == m2[0][0] && m1[1][0] == m2[1][0] && m1[2][0] == m2[2][0] && - m1[0][1] == m2[0][1] && m1[1][1] == m2[1][1] && m1[2][1] == m2[2][1] && - m1[0][2] == m2[0][2] && m1[1][2] == m2[1][2] && m1[2][2] == m2[2][2] ); + return ( m1[0][0] == m2[0][0] && m1[1][0] == m2[1][0] && m1[2][0] == m2[2][0] && + m1[0][1] == m2[0][1] && m1[1][1] == m2[1][1] && m1[2][1] == m2[2][1] && + m1[0][2] == m2[0][2] && m1[1][2] == m2[1][2] && m1[2][2] == m2[2][2] ); +} + +///for serialization +struct btMatrix3x3FloatData +{ + btVector3FloatData m_el[3]; +}; + +///for serialization +struct btMatrix3x3DoubleData +{ + btVector3DoubleData m_el[3]; +}; + + + + +SIMD_FORCE_INLINE void btMatrix3x3::serialize(struct btMatrix3x3Data& dataOut) const +{ + for (int i=0;i<3;i++) + m_el[i].serialize(dataOut.m_el[i]); } -#endif +SIMD_FORCE_INLINE void btMatrix3x3::serializeFloat(struct btMatrix3x3FloatData& dataOut) const +{ + for (int i=0;i<3;i++) + m_el[i].serializeFloat(dataOut.m_el[i]); +} + + +SIMD_FORCE_INLINE void btMatrix3x3::deSerialize(const struct btMatrix3x3Data& dataIn) +{ + for (int i=0;i<3;i++) + m_el[i].deSerialize(dataIn.m_el[i]); +} + +SIMD_FORCE_INLINE void btMatrix3x3::deSerializeFloat(const struct btMatrix3x3FloatData& dataIn) +{ + for (int i=0;i<3;i++) + m_el[i].deSerializeFloat(dataIn.m_el[i]); +} + +SIMD_FORCE_INLINE void btMatrix3x3::deSerializeDouble(const struct btMatrix3x3DoubleData& dataIn) +{ + for (int i=0;i<3;i++) + m_el[i].deSerializeDouble(dataIn.m_el[i]); +} + +#endif //BT_MATRIX3x3_H + diff --git a/extern/bullet2/src/LinearMath/btMinMax.h b/extern/bullet2/src/LinearMath/btMinMax.h index 5e27d62a4a4..80601c1e232 100644 --- a/extern/bullet2/src/LinearMath/btMinMax.h +++ b/extern/bullet2/src/LinearMath/btMinMax.h @@ -17,6 +17,8 @@ subject to the following restrictions: #ifndef GEN_MINMAX_H #define GEN_MINMAX_H +#include "LinearMath/btScalar.h" + template <class T> SIMD_FORCE_INLINE const T& btMin(const T& a, const T& b) { @@ -30,7 +32,7 @@ SIMD_FORCE_INLINE const T& btMax(const T& a, const T& b) } template <class T> -SIMD_FORCE_INLINE const T& GEN_clamped(const T& a, const T& lb, const T& ub) +SIMD_FORCE_INLINE const T& btClamped(const T& a, const T& lb, const T& ub) { return a < lb ? lb : (ub < a ? ub : a); } @@ -54,7 +56,7 @@ SIMD_FORCE_INLINE void btSetMax(T& a, const T& b) } template <class T> -SIMD_FORCE_INLINE void GEN_clamp(T& a, const T& lb, const T& ub) +SIMD_FORCE_INLINE void btClamp(T& a, const T& lb, const T& ub) { if (a < lb) { diff --git a/extern/bullet2/src/LinearMath/btPoolAllocator.h b/extern/bullet2/src/LinearMath/btPoolAllocator.h index 39d2559c747..e3b4be9b155 100644 --- a/extern/bullet2/src/LinearMath/btPoolAllocator.h +++ b/extern/bullet2/src/LinearMath/btPoolAllocator.h @@ -57,6 +57,11 @@ public: return m_freeCount; } + int getUsedCount() const + { + return m_maxElements - m_freeCount; + } + void* allocate(int size) { // release mode fix @@ -96,6 +101,15 @@ public: return m_elemSize; } + unsigned char* getPoolAddress() + { + return m_pool; + } + + const unsigned char* getPoolAddress() const + { + return m_pool; + } }; diff --git a/extern/bullet2/src/LinearMath/btQuaternion.h b/extern/bullet2/src/LinearMath/btQuaternion.h index cbeca2681cc..15cf5f868d9 100644 --- a/extern/bullet2/src/LinearMath/btQuaternion.h +++ b/extern/bullet2/src/LinearMath/btQuaternion.h @@ -209,8 +209,17 @@ public: return s; } + /**@brief Return the axis of the rotation represented by this quaternion */ + btVector3 getAxis() const + { + btScalar s_squared = btScalar(1.) - btPow(m_floats[3], btScalar(2.)); + if (s_squared < btScalar(10.) * SIMD_EPSILON) //Check for divide by zero + return btVector3(1.0, 0.0, 0.0); // Arbitrary + btScalar s = btSqrt(s_squared); + return btVector3(m_floats[0] / s, m_floats[1] / s, m_floats[2] / s); + } - /**@brief Return the inverse of this quaternion */ + /**@brief Return the inverse of this quaternion */ btQuaternion inverse() const { return btQuaternion(-m_floats[0], -m_floats[1], -m_floats[2], m_floats[3]); @@ -252,6 +261,18 @@ public: return (-qd); } + /**@todo document this and it's use */ + SIMD_FORCE_INLINE btQuaternion nearest( const btQuaternion& qd) const + { + btQuaternion diff,sum; + diff = *this - qd; + sum = *this + qd; + if( diff.dot(diff) < sum.dot(sum) ) + return qd; + return (-qd); + } + + /**@brief Return the quaternion which is the result of Spherical Linear Interpolation between this and the other quaternion * @param q The other quaternion to interpolate with * @param t The ratio between this and q to interpolate. If t = 0 the result is this, if t=1 the result is q. @@ -264,10 +285,17 @@ public: btScalar d = btScalar(1.0) / btSin(theta); btScalar s0 = btSin((btScalar(1.0) - t) * theta); btScalar s1 = btSin(t * theta); - return btQuaternion((m_floats[0] * s0 + q.x() * s1) * d, - (m_floats[1] * s0 + q.y() * s1) * d, - (m_floats[2] * s0 + q.z() * s1) * d, - (m_floats[3] * s0 + q.m_floats[3] * s1) * d); + if (dot(q) < 0) // Take care of long angle case see http://en.wikipedia.org/wiki/Slerp + return btQuaternion((m_floats[0] * s0 + -q.x() * s1) * d, + (m_floats[1] * s0 + -q.y() * s1) * d, + (m_floats[2] * s0 + -q.z() * s1) * d, + (m_floats[3] * s0 + -q.m_floats[3] * s1) * d); + else + return btQuaternion((m_floats[0] * s0 + q.x() * s1) * d, + (m_floats[1] * s0 + q.y() * s1) * d, + (m_floats[2] * s0 + q.z() * s1) * d, + (m_floats[3] * s0 + q.m_floats[3] * s1) * d); + } else { @@ -378,7 +406,11 @@ shortestArcQuat(const btVector3& v0, const btVector3& v1) // Game Programming Ge btScalar d = v0.dot(v1); if (d < -1.0 + SIMD_EPSILON) - return btQuaternion(0.0f,1.0f,0.0f,0.0f); // just pick any vector + { + btVector3 n,unused; + btPlaneSpace1(v0,n,unused); + return btQuaternion(n.x(),n.y(),n.z(),0.0f); // just pick any vector that is orthogonal to v0 + } btScalar s = btSqrt((1.0f + d) * 2.0f); btScalar rs = 1.0f / s; diff --git a/extern/bullet2/src/LinearMath/btQuickprof.cpp b/extern/bullet2/src/LinearMath/btQuickprof.cpp index 621d50427d6..14534068a0d 100644 --- a/extern/bullet2/src/LinearMath/btQuickprof.cpp +++ b/extern/bullet2/src/LinearMath/btQuickprof.cpp @@ -1,6 +1,6 @@ +/* - -/*************************************************************************************************** +*************************************************************************************************** ** ** profile.cpp ** @@ -13,13 +13,232 @@ // Credits: The Clock class was inspired by the Timer classes in // Ogre (www.ogre3d.org). -#include "LinearMath/btQuickprof.h" +#include "btQuickprof.h" +#ifndef BT_NO_PROFILE -#ifdef USE_BT_CLOCK static btClock gProfileClock; + +#ifdef __CELLOS_LV2__ +#include <sys/sys_time.h> +#include <sys/time_util.h> +#include <stdio.h> +#endif + +#if defined (SUNOS) || defined (__SUNOS__) +#include <stdio.h> +#endif + +#if defined(WIN32) || defined(_WIN32) + +#define BT_USE_WINDOWS_TIMERS +#define WIN32_LEAN_AND_MEAN +#define NOWINRES +#define NOMCX +#define NOIME + +#ifdef _XBOX + #include <Xtl.h> +#else //_XBOX + #include <windows.h> +#endif //_XBOX + +#include <time.h> + + +#else //_WIN32 +#include <sys/time.h> +#endif //_WIN32 + +#define mymin(a,b) (a > b ? a : b) + +struct btClockData +{ + +#ifdef BT_USE_WINDOWS_TIMERS + LARGE_INTEGER mClockFrequency; + DWORD mStartTick; + LONGLONG mPrevElapsedTime; + LARGE_INTEGER mStartTime; +#else +#ifdef __CELLOS_LV2__ + uint64_t mStartTime; +#else + struct timeval mStartTime; +#endif +#endif //__CELLOS_LV2__ + +}; + +///The btClock is a portable basic clock that measures accurate time in seconds, use for profiling. +btClock::btClock() +{ + m_data = new btClockData; +#ifdef BT_USE_WINDOWS_TIMERS + QueryPerformanceFrequency(&m_data->mClockFrequency); +#endif + reset(); +} + +btClock::~btClock() +{ + delete m_data; +} + +btClock::btClock(const btClock& other) +{ + m_data = new btClockData; + *m_data = *other.m_data; +} + +btClock& btClock::operator=(const btClock& other) +{ + *m_data = *other.m_data; + return *this; +} + + + /// Resets the initial reference time. +void btClock::reset() +{ +#ifdef BT_USE_WINDOWS_TIMERS + QueryPerformanceCounter(&m_data->mStartTime); + m_data->mStartTick = GetTickCount(); + m_data->mPrevElapsedTime = 0; +#else +#ifdef __CELLOS_LV2__ + + typedef uint64_t ClockSize; + ClockSize newTime; + //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); + SYS_TIMEBASE_GET( newTime ); + m_data->mStartTime = newTime; +#else + gettimeofday(&m_data->mStartTime, 0); +#endif +#endif +} + +/// Returns the time in ms since the last call to reset or since +/// the btClock was created. +unsigned long int btClock::getTimeMilliseconds() +{ +#ifdef BT_USE_WINDOWS_TIMERS + LARGE_INTEGER currentTime; + QueryPerformanceCounter(¤tTime); + LONGLONG elapsedTime = currentTime.QuadPart - + m_data->mStartTime.QuadPart; + // Compute the number of millisecond ticks elapsed. + unsigned long msecTicks = (unsigned long)(1000 * elapsedTime / + m_data->mClockFrequency.QuadPart); + // Check for unexpected leaps in the Win32 performance counter. + // (This is caused by unexpected data across the PCI to ISA + // bridge, aka south bridge. See Microsoft KB274323.) + unsigned long elapsedTicks = GetTickCount() - m_data->mStartTick; + signed long msecOff = (signed long)(msecTicks - elapsedTicks); + if (msecOff < -100 || msecOff > 100) + { + // Adjust the starting time forwards. + LONGLONG msecAdjustment = mymin(msecOff * + m_data->mClockFrequency.QuadPart / 1000, elapsedTime - + m_data->mPrevElapsedTime); + m_data->mStartTime.QuadPart += msecAdjustment; + elapsedTime -= msecAdjustment; + + // Recompute the number of millisecond ticks elapsed. + msecTicks = (unsigned long)(1000 * elapsedTime / + m_data->mClockFrequency.QuadPart); + } + + // Store the current elapsed time for adjustments next time. + m_data->mPrevElapsedTime = elapsedTime; + + return msecTicks; +#else + +#ifdef __CELLOS_LV2__ + uint64_t freq=sys_time_get_timebase_frequency(); + double dFreq=((double) freq) / 1000.0; + typedef uint64_t ClockSize; + ClockSize newTime; + SYS_TIMEBASE_GET( newTime ); + //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); + + return (unsigned long int)((double(newTime-m_data->mStartTime)) / dFreq); +#else + + struct timeval currentTime; + gettimeofday(¤tTime, 0); + return (currentTime.tv_sec - m_data->mStartTime.tv_sec) * 1000 + + (currentTime.tv_usec - m_data->mStartTime.tv_usec) / 1000; +#endif //__CELLOS_LV2__ +#endif +} + + /// Returns the time in us since the last call to reset or since + /// the Clock was created. +unsigned long int btClock::getTimeMicroseconds() +{ +#ifdef BT_USE_WINDOWS_TIMERS + LARGE_INTEGER currentTime; + QueryPerformanceCounter(¤tTime); + LONGLONG elapsedTime = currentTime.QuadPart - + m_data->mStartTime.QuadPart; + + // Compute the number of millisecond ticks elapsed. + unsigned long msecTicks = (unsigned long)(1000 * elapsedTime / + m_data->mClockFrequency.QuadPart); + + // Check for unexpected leaps in the Win32 performance counter. + // (This is caused by unexpected data across the PCI to ISA + // bridge, aka south bridge. See Microsoft KB274323.) + unsigned long elapsedTicks = GetTickCount() - m_data->mStartTick; + signed long msecOff = (signed long)(msecTicks - elapsedTicks); + if (msecOff < -100 || msecOff > 100) + { + // Adjust the starting time forwards. + LONGLONG msecAdjustment = mymin(msecOff * + m_data->mClockFrequency.QuadPart / 1000, elapsedTime - + m_data->mPrevElapsedTime); + m_data->mStartTime.QuadPart += msecAdjustment; + elapsedTime -= msecAdjustment; + } + + // Store the current elapsed time for adjustments next time. + m_data->mPrevElapsedTime = elapsedTime; + + // Convert to microseconds. + unsigned long usecTicks = (unsigned long)(1000000 * elapsedTime / + m_data->mClockFrequency.QuadPart); + + return usecTicks; +#else + +#ifdef __CELLOS_LV2__ + uint64_t freq=sys_time_get_timebase_frequency(); + double dFreq=((double) freq)/ 1000000.0; + typedef uint64_t ClockSize; + ClockSize newTime; + //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); + SYS_TIMEBASE_GET( newTime ); + + return (unsigned long int)((double(newTime-m_data->mStartTime)) / dFreq); +#else + + struct timeval currentTime; + gettimeofday(¤tTime, 0); + return (currentTime.tv_sec - m_data->mStartTime.tv_sec) * 1000000 + + (currentTime.tv_usec - m_data->mStartTime.tv_usec); +#endif//__CELLOS_LV2__ +#endif +} + + + + + inline void Profile_Get_Ticks(unsigned long int * ticks) { *ticks = gProfileClock.getTimeMicroseconds(); @@ -342,5 +561,5 @@ void CProfileManager::dumpAll() -#endif //USE_BT_CLOCK +#endif //BT_NO_PROFILE diff --git a/extern/bullet2/src/LinearMath/btQuickprof.h b/extern/bullet2/src/LinearMath/btQuickprof.h index f8d47c36861..adfbbe6149c 100644 --- a/extern/bullet2/src/LinearMath/btQuickprof.h +++ b/extern/bullet2/src/LinearMath/btQuickprof.h @@ -18,216 +18,42 @@ //To disable built-in profiling, please comment out next line //#define BT_NO_PROFILE 1 #ifndef BT_NO_PROFILE - +#include <stdio.h>//@todo remove this, backwards compatibility #include "btScalar.h" -#include "LinearMath/btAlignedAllocator.h" +#include "btAlignedAllocator.h" #include <new> -//if you don't need btClock, you can comment next line + #define USE_BT_CLOCK 1 #ifdef USE_BT_CLOCK -#ifdef __CELLOS_LV2__ -#include <sys/sys_time.h> -#include <sys/time_util.h> -#include <stdio.h> -#endif - -#if defined (SUNOS) || defined (__SUNOS__) -#include <stdio.h> -#endif - -#if defined(WIN32) || defined(_WIN32) - -#define USE_WINDOWS_TIMERS -#define WIN32_LEAN_AND_MEAN -#define NOWINRES -#define NOMCX -#define NOIME -#ifdef _XBOX -#include <Xtl.h> -#else -#include <windows.h> -#endif -#include <time.h> - -#else -#include <sys/time.h> -#endif - -#define mymin(a,b) (a > b ? a : b) ///The btClock is a portable basic clock that measures accurate time in seconds, use for profiling. class btClock { public: - btClock() - { -#ifdef USE_WINDOWS_TIMERS - QueryPerformanceFrequency(&mClockFrequency); -#endif - reset(); - } - - ~btClock() - { - } + btClock(); - /// Resets the initial reference time. - void reset() - { -#ifdef USE_WINDOWS_TIMERS - QueryPerformanceCounter(&mStartTime); - mStartTick = GetTickCount(); - mPrevElapsedTime = 0; -#else -#ifdef __CELLOS_LV2__ + btClock(const btClock& other); + btClock& operator=(const btClock& other); - typedef uint64_t ClockSize; - ClockSize newTime; - //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); - SYS_TIMEBASE_GET( newTime ); - mStartTime = newTime; -#else - gettimeofday(&mStartTime, 0); -#endif + ~btClock(); -#endif - } + /// Resets the initial reference time. + void reset(); /// Returns the time in ms since the last call to reset or since /// the btClock was created. - unsigned long int getTimeMilliseconds() - { -#ifdef USE_WINDOWS_TIMERS - LARGE_INTEGER currentTime; - QueryPerformanceCounter(¤tTime); - LONGLONG elapsedTime = currentTime.QuadPart - - mStartTime.QuadPart; - - // Compute the number of millisecond ticks elapsed. - unsigned long msecTicks = (unsigned long)(1000 * elapsedTime / - mClockFrequency.QuadPart); - - // Check for unexpected leaps in the Win32 performance counter. - // (This is caused by unexpected data across the PCI to ISA - // bridge, aka south bridge. See Microsoft KB274323.) - unsigned long elapsedTicks = GetTickCount() - mStartTick; - signed long msecOff = (signed long)(msecTicks - elapsedTicks); - if (msecOff < -100 || msecOff > 100) - { - // Adjust the starting time forwards. - LONGLONG msecAdjustment = mymin(msecOff * - mClockFrequency.QuadPart / 1000, elapsedTime - - mPrevElapsedTime); - mStartTime.QuadPart += msecAdjustment; - elapsedTime -= msecAdjustment; - - // Recompute the number of millisecond ticks elapsed. - msecTicks = (unsigned long)(1000 * elapsedTime / - mClockFrequency.QuadPart); - } - - // Store the current elapsed time for adjustments next time. - mPrevElapsedTime = elapsedTime; - - return msecTicks; -#else - -#ifdef __CELLOS_LV2__ - uint64_t freq=sys_time_get_timebase_frequency(); - double dFreq=((double) freq) / 1000.0; - typedef uint64_t ClockSize; - ClockSize newTime; - SYS_TIMEBASE_GET( newTime ); - //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); - - return (unsigned long int)((double(newTime-mStartTime)) / dFreq); -#else - - struct timeval currentTime; - gettimeofday(¤tTime, 0); - return (currentTime.tv_sec - mStartTime.tv_sec) * 1000 + - (currentTime.tv_usec - mStartTime.tv_usec) / 1000; -#endif //__CELLOS_LV2__ -#endif - } + unsigned long int getTimeMilliseconds(); /// Returns the time in us since the last call to reset or since /// the Clock was created. - unsigned long int getTimeMicroseconds() - { -#ifdef USE_WINDOWS_TIMERS - LARGE_INTEGER currentTime; - QueryPerformanceCounter(¤tTime); - LONGLONG elapsedTime = currentTime.QuadPart - - mStartTime.QuadPart; - - // Compute the number of millisecond ticks elapsed. - unsigned long msecTicks = (unsigned long)(1000 * elapsedTime / - mClockFrequency.QuadPart); - - // Check for unexpected leaps in the Win32 performance counter. - // (This is caused by unexpected data across the PCI to ISA - // bridge, aka south bridge. See Microsoft KB274323.) - unsigned long elapsedTicks = GetTickCount() - mStartTick; - signed long msecOff = (signed long)(msecTicks - elapsedTicks); - if (msecOff < -100 || msecOff > 100) - { - // Adjust the starting time forwards. - LONGLONG msecAdjustment = mymin(msecOff * - mClockFrequency.QuadPart / 1000, elapsedTime - - mPrevElapsedTime); - mStartTime.QuadPart += msecAdjustment; - elapsedTime -= msecAdjustment; - } - - // Store the current elapsed time for adjustments next time. - mPrevElapsedTime = elapsedTime; - - // Convert to microseconds. - unsigned long usecTicks = (unsigned long)(1000000 * elapsedTime / - mClockFrequency.QuadPart); - - return usecTicks; -#else - -#ifdef __CELLOS_LV2__ - uint64_t freq=sys_time_get_timebase_frequency(); - double dFreq=((double) freq)/ 1000000.0; - typedef uint64_t ClockSize; - ClockSize newTime; - //__asm __volatile__( "mftb %0" : "=r" (newTime) : : "memory"); - SYS_TIMEBASE_GET( newTime ); - - return (unsigned long int)((double(newTime-mStartTime)) / dFreq); -#else - - struct timeval currentTime; - gettimeofday(¤tTime, 0); - return (currentTime.tv_sec - mStartTime.tv_sec) * 1000000 + - (currentTime.tv_usec - mStartTime.tv_usec); -#endif//__CELLOS_LV2__ -#endif - } - + unsigned long int getTimeMicroseconds(); private: -#ifdef USE_WINDOWS_TIMERS - LARGE_INTEGER mClockFrequency; - DWORD mStartTick; - LONGLONG mPrevElapsedTime; - LARGE_INTEGER mStartTime; -#else -#ifdef __CELLOS_LV2__ - uint64_t mStartTime; -#else - struct timeval mStartTime; -#endif -#endif //__CELLOS_LV2__ - + struct btClockData* m_data; }; #endif //USE_BT_CLOCK diff --git a/extern/bullet2/src/LinearMath/btScalar.h b/extern/bullet2/src/LinearMath/btScalar.h index 08b2dee8af3..165626d530f 100644 --- a/extern/bullet2/src/LinearMath/btScalar.h +++ b/extern/bullet2/src/LinearMath/btScalar.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2003-2006 Gino van den Bergen / Erwin Coumans http://continuousphysics.com/Bullet/ +Copyright (c) 2003-2009 Erwin Coumans http://bullet.googlecode.com This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. @@ -17,15 +17,20 @@ subject to the following restrictions: #ifndef SIMD___SCALAR_H #define SIMD___SCALAR_H -#include <math.h> +#ifdef BT_MANAGED_CODE +//Aligned data types not supported in managed code +#pragma unmanaged +#endif -#include <stdlib.h>//size_t for MSVC 6.0 +#include <math.h> +#include <stdlib.h>//size_t for MSVC 6.0 #include <cstdlib> #include <cfloat> #include <float.h> -#define BT_BULLET_VERSION 274 +/* SVN $Revision$ on $Date$ from http://bullet.googlecode.com*/ +#define BT_BULLET_VERSION 278 inline int btGetVersion() { @@ -37,12 +42,13 @@ inline int btGetVersion() #endif -#ifdef WIN32 +#ifdef _WIN32 #if defined(__MINGW32__) || defined(__CYGWIN__) || (defined (_MSC_VER) && _MSC_VER < 1300) #define SIMD_FORCE_INLINE inline #define ATTRIBUTE_ALIGNED16(a) a + #define ATTRIBUTE_ALIGNED64(a) a #define ATTRIBUTE_ALIGNED128(a) a #else //#define BT_HAS_ALIGNED_ALLOCATOR @@ -53,6 +59,7 @@ inline int btGetVersion() #define SIMD_FORCE_INLINE __forceinline #define ATTRIBUTE_ALIGNED16(a) __declspec(align(16)) a + #define ATTRIBUTE_ALIGNED64(a) __declspec(align(64)) a #define ATTRIBUTE_ALIGNED128(a) __declspec (align(128)) a #ifdef _XBOX #define BT_USE_VMX128 @@ -62,7 +69,7 @@ inline int btGetVersion() #define btFsel(a,b,c) __fsel((a),(b),(c)) #else -#if (defined (WIN32) && (_MSC_VER) && _MSC_VER >= 1400) && (!defined (BT_USE_DOUBLE_PRECISION)) +#if (defined (_WIN32) && (_MSC_VER) && _MSC_VER >= 1400) && (!defined (BT_USE_DOUBLE_PRECISION)) #define BT_USE_SSE #include <emmintrin.h> #endif @@ -86,14 +93,22 @@ inline int btGetVersion() #else #if defined (__CELLOS_LV2__) - #define SIMD_FORCE_INLINE inline + #define SIMD_FORCE_INLINE inline __attribute__((always_inline)) #define ATTRIBUTE_ALIGNED16(a) a __attribute__ ((aligned (16))) + #define ATTRIBUTE_ALIGNED64(a) a __attribute__ ((aligned (64))) #define ATTRIBUTE_ALIGNED128(a) a __attribute__ ((aligned (128))) #ifndef assert #include <assert.h> #endif #ifdef BT_DEBUG - #define btAssert assert +#ifdef __SPU__ +#include <spu_printf.h> +#define printf spu_printf + #define btAssert(x) {if(!(x)){printf("Assert "__FILE__ ":%u ("#x")\n", __LINE__);spu_hcmpeq(0,0);}} +#else + #define btAssert assert +#endif + #else #define btAssert(x) #endif @@ -109,6 +124,7 @@ inline int btGetVersion() #define SIMD_FORCE_INLINE __inline #define ATTRIBUTE_ALIGNED16(a) a __attribute__ ((aligned (16))) + #define ATTRIBUTE_ALIGNED64(a) a __attribute__ ((aligned (64))) #define ATTRIBUTE_ALIGNED128(a) a __attribute__ ((aligned (128))) #ifndef assert #include <assert.h> @@ -129,11 +145,39 @@ inline int btGetVersion() #else //non-windows systems +#if (defined (__APPLE__) && defined (__i386__) && (!defined (BT_USE_DOUBLE_PRECISION))) + #define BT_USE_SSE + #include <emmintrin.h> + + #define SIMD_FORCE_INLINE inline +///@todo: check out alignment methods for other platforms/compilers + #define ATTRIBUTE_ALIGNED16(a) a __attribute__ ((aligned (16))) + #define ATTRIBUTE_ALIGNED64(a) a __attribute__ ((aligned (64))) + #define ATTRIBUTE_ALIGNED128(a) a __attribute__ ((aligned (128))) + #ifndef assert + #include <assert.h> + #endif + + #if defined(DEBUG) || defined (_DEBUG) + #define btAssert assert + #else + #define btAssert(x) + #endif + + //btFullAssert is optional, slows down a lot + #define btFullAssert(x) + #define btLikely(_c) _c + #define btUnlikely(_c) _c + +#else + #define SIMD_FORCE_INLINE inline ///@todo: check out alignment methods for other platforms/compilers ///#define ATTRIBUTE_ALIGNED16(a) a __attribute__ ((aligned (16))) + ///#define ATTRIBUTE_ALIGNED64(a) a __attribute__ ((aligned (64))) ///#define ATTRIBUTE_ALIGNED128(a) a __attribute__ ((aligned (128))) #define ATTRIBUTE_ALIGNED16(a) a + #define ATTRIBUTE_ALIGNED64(a) a #define ATTRIBUTE_ALIGNED128(a) a #ifndef assert #include <assert.h> @@ -149,21 +193,13 @@ inline int btGetVersion() #define btFullAssert(x) #define btLikely(_c) _c #define btUnlikely(_c) _c - +#endif //__APPLE__ #endif // LIBSPE2 #endif //__CELLOS_LV2__ #endif -/// older compilers (gcc 3.x) and Sun needs double version of sqrt etc. -/// exclude Apple Intel (i's assumed to be a Macbook or new Intel Dual Core Processor) -#if defined (__sun) || defined (__sun__) || defined (__sparc) || (defined (__APPLE__) && ! defined (__i386__)) -//use slow double float precision operation on those platforms -#ifndef BT_USE_DOUBLE_PRECISION -#define BT_FORCE_DOUBLE_FUNCTIONS -#endif -#endif ///The btScalar type abstracts floating point numbers, to easily switch between double and single floating point precision. #if defined(BT_USE_DOUBLE_PRECISION) @@ -197,13 +233,14 @@ SIMD_FORCE_INLINE btScalar btFabs(btScalar x) { return fabs(x); } SIMD_FORCE_INLINE btScalar btCos(btScalar x) { return cos(x); } SIMD_FORCE_INLINE btScalar btSin(btScalar x) { return sin(x); } SIMD_FORCE_INLINE btScalar btTan(btScalar x) { return tan(x); } -SIMD_FORCE_INLINE btScalar btAcos(btScalar x) { return acos(x); } -SIMD_FORCE_INLINE btScalar btAsin(btScalar x) { return asin(x); } +SIMD_FORCE_INLINE btScalar btAcos(btScalar x) { if (x<btScalar(-1)) x=btScalar(-1); if (x>btScalar(1)) x=btScalar(1); return acos(x); } +SIMD_FORCE_INLINE btScalar btAsin(btScalar x) { if (x<btScalar(-1)) x=btScalar(-1); if (x>btScalar(1)) x=btScalar(1); return asin(x); } SIMD_FORCE_INLINE btScalar btAtan(btScalar x) { return atan(x); } SIMD_FORCE_INLINE btScalar btAtan2(btScalar x, btScalar y) { return atan2(x, y); } SIMD_FORCE_INLINE btScalar btExp(btScalar x) { return exp(x); } SIMD_FORCE_INLINE btScalar btLog(btScalar x) { return log(x); } SIMD_FORCE_INLINE btScalar btPow(btScalar x,btScalar y) { return pow(x,y); } +SIMD_FORCE_INLINE btScalar btFmod(btScalar x,btScalar y) { return fmod(x,y); } #else @@ -216,7 +253,7 @@ SIMD_FORCE_INLINE btScalar btSqrt(btScalar y) tempf = y; *tfptr = (0xbfcdd90a - *tfptr)>>1; /* estimate of 1/sqrt(y) */ x = tempf; - z = y*btScalar(0.5); /* hoist out the “/2” */ + z = y*btScalar(0.5); x = (btScalar(1.5)*x)-(x*x)*(x*z); /* iteration formula */ x = (btScalar(1.5)*x)-(x*x)*(x*z); x = (btScalar(1.5)*x)-(x*x)*(x*z); @@ -232,15 +269,25 @@ SIMD_FORCE_INLINE btScalar btCos(btScalar x) { return cosf(x); } SIMD_FORCE_INLINE btScalar btSin(btScalar x) { return sinf(x); } SIMD_FORCE_INLINE btScalar btTan(btScalar x) { return tanf(x); } SIMD_FORCE_INLINE btScalar btAcos(btScalar x) { - btAssert(x <= btScalar(1.)); + if (x<btScalar(-1)) + x=btScalar(-1); + if (x>btScalar(1)) + x=btScalar(1); return acosf(x); } -SIMD_FORCE_INLINE btScalar btAsin(btScalar x) { return asinf(x); } +SIMD_FORCE_INLINE btScalar btAsin(btScalar x) { + if (x<btScalar(-1)) + x=btScalar(-1); + if (x>btScalar(1)) + x=btScalar(1); + return asinf(x); +} SIMD_FORCE_INLINE btScalar btAtan(btScalar x) { return atanf(x); } SIMD_FORCE_INLINE btScalar btAtan2(btScalar x, btScalar y) { return atan2f(x, y); } SIMD_FORCE_INLINE btScalar btExp(btScalar x) { return expf(x); } SIMD_FORCE_INLINE btScalar btLog(btScalar x) { return logf(x); } SIMD_FORCE_INLINE btScalar btPow(btScalar x,btScalar y) { return powf(x,y); } +SIMD_FORCE_INLINE btScalar btFmod(btScalar x,btScalar y) { return fmodf(x,y); } #endif @@ -249,6 +296,10 @@ SIMD_FORCE_INLINE btScalar btPow(btScalar x,btScalar y) { return powf(x,y); } #define SIMD_HALF_PI (SIMD_2_PI * btScalar(0.25)) #define SIMD_RADS_PER_DEG (SIMD_2_PI / btScalar(360.0)) #define SIMD_DEGS_PER_RAD (btScalar(360.0) / SIMD_2_PI) +#define SIMDSQRT12 btScalar(0.7071067811865475244008443621048490) + +#define btRecipSqrt(x) ((btScalar)(btScalar(1.0)/btSqrt(btScalar(x)))) /* reciprocal square root */ + #ifdef BT_USE_DOUBLE_PRECISION #define SIMD_EPSILON DBL_EPSILON @@ -439,5 +490,35 @@ SIMD_FORCE_INLINE double btUnswapEndianDouble(const unsigned char *src) return d; } +// returns normalized value in range [-SIMD_PI, SIMD_PI] +SIMD_FORCE_INLINE btScalar btNormalizeAngle(btScalar angleInRadians) +{ + angleInRadians = btFmod(angleInRadians, SIMD_2_PI); + if(angleInRadians < -SIMD_PI) + { + return angleInRadians + SIMD_2_PI; + } + else if(angleInRadians > SIMD_PI) + { + return angleInRadians - SIMD_2_PI; + } + else + { + return angleInRadians; + } +} +///rudimentary class to provide type info +struct btTypedObject +{ + btTypedObject(int objectType) + :m_objectType(objectType) + { + } + int m_objectType; + inline int getObjectType() const + { + return m_objectType; + } +}; #endif //SIMD___SCALAR_H diff --git a/extern/bullet2/src/LinearMath/btSerializer.cpp b/extern/bullet2/src/LinearMath/btSerializer.cpp new file mode 100644 index 00000000000..c6d387e6133 --- /dev/null +++ b/extern/bullet2/src/LinearMath/btSerializer.cpp @@ -0,0 +1,832 @@ +unsigned char sBulletDNAstr[]= { +83,68,78,65,78,65,77,69,42,1,0,0,109,95,115,105,122,101,0,109, +95,99,97,112,97,99,105,116,121,0,42,109,95,100,97,116,97,0,109,95, +99,111,108,108,105,115,105,111,110,83,104,97,112,101,115,0,109,95,99,111, +108,108,105,115,105,111,110,79,98,106,101,99,116,115,0,109,95,99,111,110, +115,116,114,97,105,110,116,115,0,42,102,105,114,115,116,0,42,108,97,115, +116,0,109,95,102,108,111,97,116,115,91,52,93,0,109,95,101,108,91,51, +93,0,109,95,98,97,115,105,115,0,109,95,111,114,105,103,105,110,0,109, +95,114,111,111,116,78,111,100,101,73,110,100,101,120,0,109,95,115,117,98, +116,114,101,101,83,105,122,101,0,109,95,113,117,97,110,116,105,122,101,100, +65,97,98,98,77,105,110,91,51,93,0,109,95,113,117,97,110,116,105,122, +101,100,65,97,98,98,77,97,120,91,51,93,0,109,95,97,97,98,98,77, +105,110,79,114,103,0,109,95,97,97,98,98,77,97,120,79,114,103,0,109, +95,101,115,99,97,112,101,73,110,100,101,120,0,109,95,115,117,98,80,97, +114,116,0,109,95,116,114,105,97,110,103,108,101,73,110,100,101,120,0,109, +95,112,97,100,91,52,93,0,109,95,101,115,99,97,112,101,73,110,100,101, +120,79,114,84,114,105,97,110,103,108,101,73,110,100,101,120,0,109,95,98, +118,104,65,97,98,98,77,105,110,0,109,95,98,118,104,65,97,98,98,77, +97,120,0,109,95,98,118,104,81,117,97,110,116,105,122,97,116,105,111,110, +0,109,95,99,117,114,78,111,100,101,73,110,100,101,120,0,109,95,117,115, +101,81,117,97,110,116,105,122,97,116,105,111,110,0,109,95,110,117,109,67, +111,110,116,105,103,117,111,117,115,76,101,97,102,78,111,100,101,115,0,109, +95,110,117,109,81,117,97,110,116,105,122,101,100,67,111,110,116,105,103,117, +111,117,115,78,111,100,101,115,0,42,109,95,99,111,110,116,105,103,117,111, +117,115,78,111,100,101,115,80,116,114,0,42,109,95,113,117,97,110,116,105, +122,101,100,67,111,110,116,105,103,117,111,117,115,78,111,100,101,115,80,116, +114,0,42,109,95,115,117,98,84,114,101,101,73,110,102,111,80,116,114,0, +109,95,116,114,97,118,101,114,115,97,108,77,111,100,101,0,109,95,110,117, +109,83,117,98,116,114,101,101,72,101,97,100,101,114,115,0,42,109,95,110, +97,109,101,0,109,95,115,104,97,112,101,84,121,112,101,0,109,95,112,97, +100,100,105,110,103,91,52,93,0,109,95,99,111,108,108,105,115,105,111,110, +83,104,97,112,101,68,97,116,97,0,109,95,108,111,99,97,108,83,99,97, +108,105,110,103,0,109,95,112,108,97,110,101,78,111,114,109,97,108,0,109, +95,112,108,97,110,101,67,111,110,115,116,97,110,116,0,109,95,105,109,112, +108,105,99,105,116,83,104,97,112,101,68,105,109,101,110,115,105,111,110,115, +0,109,95,99,111,108,108,105,115,105,111,110,77,97,114,103,105,110,0,109, +95,112,97,100,100,105,110,103,0,109,95,112,111,115,0,109,95,114,97,100, +105,117,115,0,109,95,99,111,110,118,101,120,73,110,116,101,114,110,97,108, +83,104,97,112,101,68,97,116,97,0,42,109,95,108,111,99,97,108,80,111, +115,105,116,105,111,110,65,114,114,97,121,80,116,114,0,109,95,108,111,99, +97,108,80,111,115,105,116,105,111,110,65,114,114,97,121,83,105,122,101,0, +109,95,118,97,108,117,101,0,109,95,112,97,100,91,50,93,0,109,95,118, +97,108,117,101,115,91,51,93,0,109,95,112,97,100,0,42,109,95,118,101, +114,116,105,99,101,115,51,102,0,42,109,95,118,101,114,116,105,99,101,115, +51,100,0,42,109,95,105,110,100,105,99,101,115,51,50,0,42,109,95,51, +105,110,100,105,99,101,115,49,54,0,42,109,95,51,105,110,100,105,99,101, +115,56,0,42,109,95,105,110,100,105,99,101,115,49,54,0,109,95,110,117, +109,84,114,105,97,110,103,108,101,115,0,109,95,110,117,109,86,101,114,116, +105,99,101,115,0,42,109,95,109,101,115,104,80,97,114,116,115,80,116,114, +0,109,95,115,99,97,108,105,110,103,0,109,95,110,117,109,77,101,115,104, +80,97,114,116,115,0,109,95,109,101,115,104,73,110,116,101,114,102,97,99, +101,0,42,109,95,113,117,97,110,116,105,122,101,100,70,108,111,97,116,66, +118,104,0,42,109,95,113,117,97,110,116,105,122,101,100,68,111,117,98,108, +101,66,118,104,0,42,109,95,116,114,105,97,110,103,108,101,73,110,102,111, +77,97,112,0,109,95,112,97,100,51,91,52,93,0,109,95,116,114,105,109, +101,115,104,83,104,97,112,101,68,97,116,97,0,109,95,116,114,97,110,115, +102,111,114,109,0,42,109,95,99,104,105,108,100,83,104,97,112,101,0,109, +95,99,104,105,108,100,83,104,97,112,101,84,121,112,101,0,109,95,99,104, +105,108,100,77,97,114,103,105,110,0,42,109,95,99,104,105,108,100,83,104, +97,112,101,80,116,114,0,109,95,110,117,109,67,104,105,108,100,83,104,97, +112,101,115,0,109,95,117,112,65,120,105,115,0,109,95,102,108,97,103,115, +0,109,95,101,100,103,101,86,48,86,49,65,110,103,108,101,0,109,95,101, +100,103,101,86,49,86,50,65,110,103,108,101,0,109,95,101,100,103,101,86, +50,86,48,65,110,103,108,101,0,42,109,95,104,97,115,104,84,97,98,108, +101,80,116,114,0,42,109,95,110,101,120,116,80,116,114,0,42,109,95,118, +97,108,117,101,65,114,114,97,121,80,116,114,0,42,109,95,107,101,121,65, +114,114,97,121,80,116,114,0,109,95,99,111,110,118,101,120,69,112,115,105, +108,111,110,0,109,95,112,108,97,110,97,114,69,112,115,105,108,111,110,0, +109,95,101,113,117,97,108,86,101,114,116,101,120,84,104,114,101,115,104,111, +108,100,0,109,95,101,100,103,101,68,105,115,116,97,110,99,101,84,104,114, +101,115,104,111,108,100,0,109,95,122,101,114,111,65,114,101,97,84,104,114, +101,115,104,111,108,100,0,109,95,110,101,120,116,83,105,122,101,0,109,95, +104,97,115,104,84,97,98,108,101,83,105,122,101,0,109,95,110,117,109,86, +97,108,117,101,115,0,109,95,110,117,109,75,101,121,115,0,109,95,103,105, +109,112,97,99,116,83,117,98,84,121,112,101,0,42,109,95,117,110,115,99, +97,108,101,100,80,111,105,110,116,115,70,108,111,97,116,80,116,114,0,42, +109,95,117,110,115,99,97,108,101,100,80,111,105,110,116,115,68,111,117,98, +108,101,80,116,114,0,109,95,110,117,109,85,110,115,99,97,108,101,100,80, +111,105,110,116,115,0,109,95,112,97,100,100,105,110,103,51,91,52,93,0, +42,109,95,98,114,111,97,100,112,104,97,115,101,72,97,110,100,108,101,0, +42,109,95,99,111,108,108,105,115,105,111,110,83,104,97,112,101,0,42,109, +95,114,111,111,116,67,111,108,108,105,115,105,111,110,83,104,97,112,101,0, +109,95,119,111,114,108,100,84,114,97,110,115,102,111,114,109,0,109,95,105, +110,116,101,114,112,111,108,97,116,105,111,110,87,111,114,108,100,84,114,97, +110,115,102,111,114,109,0,109,95,105,110,116,101,114,112,111,108,97,116,105, +111,110,76,105,110,101,97,114,86,101,108,111,99,105,116,121,0,109,95,105, +110,116,101,114,112,111,108,97,116,105,111,110,65,110,103,117,108,97,114,86, +101,108,111,99,105,116,121,0,109,95,97,110,105,115,111,116,114,111,112,105, +99,70,114,105,99,116,105,111,110,0,109,95,99,111,110,116,97,99,116,80, +114,111,99,101,115,115,105,110,103,84,104,114,101,115,104,111,108,100,0,109, +95,100,101,97,99,116,105,118,97,116,105,111,110,84,105,109,101,0,109,95, +102,114,105,99,116,105,111,110,0,109,95,114,101,115,116,105,116,117,116,105, +111,110,0,109,95,104,105,116,70,114,97,99,116,105,111,110,0,109,95,99, +99,100,83,119,101,112,116,83,112,104,101,114,101,82,97,100,105,117,115,0, +109,95,99,99,100,77,111,116,105,111,110,84,104,114,101,115,104,111,108,100, +0,109,95,104,97,115,65,110,105,115,111,116,114,111,112,105,99,70,114,105, +99,116,105,111,110,0,109,95,99,111,108,108,105,115,105,111,110,70,108,97, +103,115,0,109,95,105,115,108,97,110,100,84,97,103,49,0,109,95,99,111, +109,112,97,110,105,111,110,73,100,0,109,95,97,99,116,105,118,97,116,105, +111,110,83,116,97,116,101,49,0,109,95,105,110,116,101,114,110,97,108,84, +121,112,101,0,109,95,99,104,101,99,107,67,111,108,108,105,100,101,87,105, +116,104,0,109,95,99,111,108,108,105,115,105,111,110,79,98,106,101,99,116, +68,97,116,97,0,109,95,105,110,118,73,110,101,114,116,105,97,84,101,110, +115,111,114,87,111,114,108,100,0,109,95,108,105,110,101,97,114,86,101,108, +111,99,105,116,121,0,109,95,97,110,103,117,108,97,114,86,101,108,111,99, +105,116,121,0,109,95,97,110,103,117,108,97,114,70,97,99,116,111,114,0, +109,95,108,105,110,101,97,114,70,97,99,116,111,114,0,109,95,103,114,97, +118,105,116,121,0,109,95,103,114,97,118,105,116,121,95,97,99,99,101,108, +101,114,97,116,105,111,110,0,109,95,105,110,118,73,110,101,114,116,105,97, +76,111,99,97,108,0,109,95,116,111,116,97,108,70,111,114,99,101,0,109, +95,116,111,116,97,108,84,111,114,113,117,101,0,109,95,105,110,118,101,114, +115,101,77,97,115,115,0,109,95,108,105,110,101,97,114,68,97,109,112,105, +110,103,0,109,95,97,110,103,117,108,97,114,68,97,109,112,105,110,103,0, +109,95,97,100,100,105,116,105,111,110,97,108,68,97,109,112,105,110,103,70, +97,99,116,111,114,0,109,95,97,100,100,105,116,105,111,110,97,108,76,105, +110,101,97,114,68,97,109,112,105,110,103,84,104,114,101,115,104,111,108,100, +83,113,114,0,109,95,97,100,100,105,116,105,111,110,97,108,65,110,103,117, +108,97,114,68,97,109,112,105,110,103,84,104,114,101,115,104,111,108,100,83, +113,114,0,109,95,97,100,100,105,116,105,111,110,97,108,65,110,103,117,108, +97,114,68,97,109,112,105,110,103,70,97,99,116,111,114,0,109,95,108,105, +110,101,97,114,83,108,101,101,112,105,110,103,84,104,114,101,115,104,111,108, +100,0,109,95,97,110,103,117,108,97,114,83,108,101,101,112,105,110,103,84, +104,114,101,115,104,111,108,100,0,109,95,97,100,100,105,116,105,111,110,97, +108,68,97,109,112,105,110,103,0,109,95,110,117,109,67,111,110,115,116,114, +97,105,110,116,82,111,119,115,0,110,117,98,0,42,109,95,114,98,65,0, +42,109,95,114,98,66,0,109,95,111,98,106,101,99,116,84,121,112,101,0, +109,95,117,115,101,114,67,111,110,115,116,114,97,105,110,116,84,121,112,101, +0,109,95,117,115,101,114,67,111,110,115,116,114,97,105,110,116,73,100,0, +109,95,110,101,101,100,115,70,101,101,100,98,97,99,107,0,109,95,97,112, +112,108,105,101,100,73,109,112,117,108,115,101,0,109,95,100,98,103,68,114, +97,119,83,105,122,101,0,109,95,100,105,115,97,98,108,101,67,111,108,108, +105,115,105,111,110,115,66,101,116,119,101,101,110,76,105,110,107,101,100,66, +111,100,105,101,115,0,109,95,112,97,100,52,91,52,93,0,109,95,116,121, +112,101,67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,109,95,112, +105,118,111,116,73,110,65,0,109,95,112,105,118,111,116,73,110,66,0,109, +95,114,98,65,70,114,97,109,101,0,109,95,114,98,66,70,114,97,109,101, +0,109,95,117,115,101,82,101,102,101,114,101,110,99,101,70,114,97,109,101, +65,0,109,95,97,110,103,117,108,97,114,79,110,108,121,0,109,95,101,110, +97,98,108,101,65,110,103,117,108,97,114,77,111,116,111,114,0,109,95,109, +111,116,111,114,84,97,114,103,101,116,86,101,108,111,99,105,116,121,0,109, +95,109,97,120,77,111,116,111,114,73,109,112,117,108,115,101,0,109,95,108, +111,119,101,114,76,105,109,105,116,0,109,95,117,112,112,101,114,76,105,109, +105,116,0,109,95,108,105,109,105,116,83,111,102,116,110,101,115,115,0,109, +95,98,105,97,115,70,97,99,116,111,114,0,109,95,114,101,108,97,120,97, +116,105,111,110,70,97,99,116,111,114,0,109,95,115,119,105,110,103,83,112, +97,110,49,0,109,95,115,119,105,110,103,83,112,97,110,50,0,109,95,116, +119,105,115,116,83,112,97,110,0,109,95,100,97,109,112,105,110,103,0,109, +95,108,105,110,101,97,114,85,112,112,101,114,76,105,109,105,116,0,109,95, +108,105,110,101,97,114,76,111,119,101,114,76,105,109,105,116,0,109,95,97, +110,103,117,108,97,114,85,112,112,101,114,76,105,109,105,116,0,109,95,97, +110,103,117,108,97,114,76,111,119,101,114,76,105,109,105,116,0,109,95,117, +115,101,76,105,110,101,97,114,82,101,102,101,114,101,110,99,101,70,114,97, +109,101,65,0,109,95,117,115,101,79,102,102,115,101,116,70,111,114,67,111, +110,115,116,114,97,105,110,116,70,114,97,109,101,0,109,95,54,100,111,102, +68,97,116,97,0,109,95,115,112,114,105,110,103,69,110,97,98,108,101,100, +91,54,93,0,109,95,101,113,117,105,108,105,98,114,105,117,109,80,111,105, +110,116,91,54,93,0,109,95,115,112,114,105,110,103,83,116,105,102,102,110, +101,115,115,91,54,93,0,109,95,115,112,114,105,110,103,68,97,109,112,105, +110,103,91,54,93,0,109,95,108,105,110,101,97,114,83,116,105,102,102,110, +101,115,115,0,109,95,97,110,103,117,108,97,114,83,116,105,102,102,110,101, +115,115,0,109,95,118,111,108,117,109,101,83,116,105,102,102,110,101,115,115, +0,42,109,95,109,97,116,101,114,105,97,108,0,109,95,112,111,115,105,116, +105,111,110,0,109,95,112,114,101,118,105,111,117,115,80,111,115,105,116,105, +111,110,0,109,95,118,101,108,111,99,105,116,121,0,109,95,97,99,99,117, +109,117,108,97,116,101,100,70,111,114,99,101,0,109,95,110,111,114,109,97, +108,0,109,95,97,114,101,97,0,109,95,97,116,116,97,99,104,0,109,95, +110,111,100,101,73,110,100,105,99,101,115,91,50,93,0,109,95,114,101,115, +116,76,101,110,103,116,104,0,109,95,98,98,101,110,100,105,110,103,0,109, +95,110,111,100,101,73,110,100,105,99,101,115,91,51,93,0,109,95,114,101, +115,116,65,114,101,97,0,109,95,99,48,91,52,93,0,109,95,110,111,100, +101,73,110,100,105,99,101,115,91,52,93,0,109,95,114,101,115,116,86,111, +108,117,109,101,0,109,95,99,49,0,109,95,99,50,0,109,95,99,48,0, +109,95,108,111,99,97,108,70,114,97,109,101,0,42,109,95,114,105,103,105, +100,66,111,100,121,0,109,95,110,111,100,101,73,110,100,101,120,0,109,95, +97,101,114,111,77,111,100,101,108,0,109,95,98,97,117,109,103,97,114,116, +101,0,109,95,100,114,97,103,0,109,95,108,105,102,116,0,109,95,112,114, +101,115,115,117,114,101,0,109,95,118,111,108,117,109,101,0,109,95,100,121, +110,97,109,105,99,70,114,105,99,116,105,111,110,0,109,95,112,111,115,101, +77,97,116,99,104,0,109,95,114,105,103,105,100,67,111,110,116,97,99,116, +72,97,114,100,110,101,115,115,0,109,95,107,105,110,101,116,105,99,67,111, +110,116,97,99,116,72,97,114,100,110,101,115,115,0,109,95,115,111,102,116, +67,111,110,116,97,99,116,72,97,114,100,110,101,115,115,0,109,95,97,110, +99,104,111,114,72,97,114,100,110,101,115,115,0,109,95,115,111,102,116,82, +105,103,105,100,67,108,117,115,116,101,114,72,97,114,100,110,101,115,115,0, +109,95,115,111,102,116,75,105,110,101,116,105,99,67,108,117,115,116,101,114, +72,97,114,100,110,101,115,115,0,109,95,115,111,102,116,83,111,102,116,67, +108,117,115,116,101,114,72,97,114,100,110,101,115,115,0,109,95,115,111,102, +116,82,105,103,105,100,67,108,117,115,116,101,114,73,109,112,117,108,115,101, +83,112,108,105,116,0,109,95,115,111,102,116,75,105,110,101,116,105,99,67, +108,117,115,116,101,114,73,109,112,117,108,115,101,83,112,108,105,116,0,109, +95,115,111,102,116,83,111,102,116,67,108,117,115,116,101,114,73,109,112,117, +108,115,101,83,112,108,105,116,0,109,95,109,97,120,86,111,108,117,109,101, +0,109,95,116,105,109,101,83,99,97,108,101,0,109,95,118,101,108,111,99, +105,116,121,73,116,101,114,97,116,105,111,110,115,0,109,95,112,111,115,105, +116,105,111,110,73,116,101,114,97,116,105,111,110,115,0,109,95,100,114,105, +102,116,73,116,101,114,97,116,105,111,110,115,0,109,95,99,108,117,115,116, +101,114,73,116,101,114,97,116,105,111,110,115,0,109,95,114,111,116,0,109, +95,115,99,97,108,101,0,109,95,97,113,113,0,109,95,99,111,109,0,42, +109,95,112,111,115,105,116,105,111,110,115,0,42,109,95,119,101,105,103,104, +116,115,0,109,95,110,117,109,80,111,115,105,116,105,111,110,115,0,109,95, +110,117,109,87,101,105,103,116,115,0,109,95,98,118,111,108,117,109,101,0, +109,95,98,102,114,97,109,101,0,109,95,102,114,97,109,101,120,102,111,114, +109,0,109,95,108,111,99,105,105,0,109,95,105,110,118,119,105,0,109,95, +118,105,109,112,117,108,115,101,115,91,50,93,0,109,95,100,105,109,112,117, +108,115,101,115,91,50,93,0,109,95,108,118,0,109,95,97,118,0,42,109, +95,102,114,97,109,101,114,101,102,115,0,42,109,95,110,111,100,101,73,110, +100,105,99,101,115,0,42,109,95,109,97,115,115,101,115,0,109,95,110,117, +109,70,114,97,109,101,82,101,102,115,0,109,95,110,117,109,78,111,100,101, +115,0,109,95,110,117,109,77,97,115,115,101,115,0,109,95,105,100,109,97, +115,115,0,109,95,105,109,97,115,115,0,109,95,110,118,105,109,112,117,108, +115,101,115,0,109,95,110,100,105,109,112,117,108,115,101,115,0,109,95,110, +100,97,109,112,105,110,103,0,109,95,108,100,97,109,112,105,110,103,0,109, +95,97,100,97,109,112,105,110,103,0,109,95,109,97,116,99,104,105,110,103, +0,109,95,109,97,120,83,101,108,102,67,111,108,108,105,115,105,111,110,73, +109,112,117,108,115,101,0,109,95,115,101,108,102,67,111,108,108,105,115,105, +111,110,73,109,112,117,108,115,101,70,97,99,116,111,114,0,109,95,99,111, +110,116,97,105,110,115,65,110,99,104,111,114,0,109,95,99,111,108,108,105, +100,101,0,109,95,99,108,117,115,116,101,114,73,110,100,101,120,0,42,109, +95,98,111,100,121,65,0,42,109,95,98,111,100,121,66,0,109,95,114,101, +102,115,91,50,93,0,109,95,99,102,109,0,109,95,101,114,112,0,109,95, +115,112,108,105,116,0,109,95,100,101,108,101,116,101,0,109,95,114,101,108, +80,111,115,105,116,105,111,110,91,50,93,0,109,95,98,111,100,121,65,116, +121,112,101,0,109,95,98,111,100,121,66,116,121,112,101,0,109,95,106,111, +105,110,116,84,121,112,101,0,42,109,95,112,111,115,101,0,42,42,109,95, +109,97,116,101,114,105,97,108,115,0,42,109,95,110,111,100,101,115,0,42, +109,95,108,105,110,107,115,0,42,109,95,102,97,99,101,115,0,42,109,95, +116,101,116,114,97,104,101,100,114,97,0,42,109,95,97,110,99,104,111,114, +115,0,42,109,95,99,108,117,115,116,101,114,115,0,42,109,95,106,111,105, +110,116,115,0,109,95,110,117,109,77,97,116,101,114,105,97,108,115,0,109, +95,110,117,109,76,105,110,107,115,0,109,95,110,117,109,70,97,99,101,115, +0,109,95,110,117,109,84,101,116,114,97,104,101,100,114,97,0,109,95,110, +117,109,65,110,99,104,111,114,115,0,109,95,110,117,109,67,108,117,115,116, +101,114,115,0,109,95,110,117,109,74,111,105,110,116,115,0,109,95,99,111, +110,102,105,103,0,0,0,0,84,89,80,69,72,0,0,0,99,104,97,114, +0,117,99,104,97,114,0,115,104,111,114,116,0,117,115,104,111,114,116,0, +105,110,116,0,108,111,110,103,0,117,108,111,110,103,0,102,108,111,97,116, +0,100,111,117,98,108,101,0,118,111,105,100,0,80,111,105,110,116,101,114, +65,114,114,97,121,0,98,116,80,104,121,115,105,99,115,83,121,115,116,101, +109,0,76,105,115,116,66,97,115,101,0,98,116,86,101,99,116,111,114,51, +70,108,111,97,116,68,97,116,97,0,98,116,86,101,99,116,111,114,51,68, +111,117,98,108,101,68,97,116,97,0,98,116,77,97,116,114,105,120,51,120, +51,70,108,111,97,116,68,97,116,97,0,98,116,77,97,116,114,105,120,51, +120,51,68,111,117,98,108,101,68,97,116,97,0,98,116,84,114,97,110,115, +102,111,114,109,70,108,111,97,116,68,97,116,97,0,98,116,84,114,97,110, +115,102,111,114,109,68,111,117,98,108,101,68,97,116,97,0,98,116,66,118, +104,83,117,98,116,114,101,101,73,110,102,111,68,97,116,97,0,98,116,79, +112,116,105,109,105,122,101,100,66,118,104,78,111,100,101,70,108,111,97,116, +68,97,116,97,0,98,116,79,112,116,105,109,105,122,101,100,66,118,104,78, +111,100,101,68,111,117,98,108,101,68,97,116,97,0,98,116,81,117,97,110, +116,105,122,101,100,66,118,104,78,111,100,101,68,97,116,97,0,98,116,81, +117,97,110,116,105,122,101,100,66,118,104,70,108,111,97,116,68,97,116,97, +0,98,116,81,117,97,110,116,105,122,101,100,66,118,104,68,111,117,98,108, +101,68,97,116,97,0,98,116,67,111,108,108,105,115,105,111,110,83,104,97, +112,101,68,97,116,97,0,98,116,83,116,97,116,105,99,80,108,97,110,101, +83,104,97,112,101,68,97,116,97,0,98,116,67,111,110,118,101,120,73,110, +116,101,114,110,97,108,83,104,97,112,101,68,97,116,97,0,98,116,80,111, +115,105,116,105,111,110,65,110,100,82,97,100,105,117,115,0,98,116,77,117, +108,116,105,83,112,104,101,114,101,83,104,97,112,101,68,97,116,97,0,98, +116,73,110,116,73,110,100,101,120,68,97,116,97,0,98,116,83,104,111,114, +116,73,110,116,73,110,100,101,120,68,97,116,97,0,98,116,83,104,111,114, +116,73,110,116,73,110,100,101,120,84,114,105,112,108,101,116,68,97,116,97, +0,98,116,67,104,97,114,73,110,100,101,120,84,114,105,112,108,101,116,68, +97,116,97,0,98,116,77,101,115,104,80,97,114,116,68,97,116,97,0,98, +116,83,116,114,105,100,105,110,103,77,101,115,104,73,110,116,101,114,102,97, +99,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108,101,77,101,115, +104,83,104,97,112,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108, +101,73,110,102,111,77,97,112,68,97,116,97,0,98,116,83,99,97,108,101, +100,84,114,105,97,110,103,108,101,77,101,115,104,83,104,97,112,101,68,97, +116,97,0,98,116,67,111,109,112,111,117,110,100,83,104,97,112,101,67,104, +105,108,100,68,97,116,97,0,98,116,67,111,109,112,111,117,110,100,83,104, +97,112,101,68,97,116,97,0,98,116,67,121,108,105,110,100,101,114,83,104, +97,112,101,68,97,116,97,0,98,116,67,97,112,115,117,108,101,83,104,97, +112,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108,101,73,110,102, +111,68,97,116,97,0,98,116,71,73,109,112,97,99,116,77,101,115,104,83, +104,97,112,101,68,97,116,97,0,98,116,67,111,110,118,101,120,72,117,108, +108,83,104,97,112,101,68,97,116,97,0,98,116,67,111,108,108,105,115,105, +111,110,79,98,106,101,99,116,68,111,117,98,108,101,68,97,116,97,0,98, +116,67,111,108,108,105,115,105,111,110,79,98,106,101,99,116,70,108,111,97, +116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121,70,108,111, +97,116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121,68,111, +117,98,108,101,68,97,116,97,0,98,116,67,111,110,115,116,114,97,105,110, +116,73,110,102,111,49,0,98,116,84,121,112,101,100,67,111,110,115,116,114, +97,105,110,116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121, +68,97,116,97,0,98,116,80,111,105,110,116,50,80,111,105,110,116,67,111, +110,115,116,114,97,105,110,116,70,108,111,97,116,68,97,116,97,0,98,116, +80,111,105,110,116,50,80,111,105,110,116,67,111,110,115,116,114,97,105,110, +116,68,111,117,98,108,101,68,97,116,97,0,98,116,72,105,110,103,101,67, +111,110,115,116,114,97,105,110,116,68,111,117,98,108,101,68,97,116,97,0, +98,116,72,105,110,103,101,67,111,110,115,116,114,97,105,110,116,70,108,111, +97,116,68,97,116,97,0,98,116,67,111,110,101,84,119,105,115,116,67,111, +110,115,116,114,97,105,110,116,68,97,116,97,0,98,116,71,101,110,101,114, +105,99,54,68,111,102,67,111,110,115,116,114,97,105,110,116,68,97,116,97, +0,98,116,71,101,110,101,114,105,99,54,68,111,102,83,112,114,105,110,103, +67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,98,116,83,108,105, +100,101,114,67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,83,111, +102,116,66,111,100,121,77,97,116,101,114,105,97,108,68,97,116,97,0,83, +111,102,116,66,111,100,121,78,111,100,101,68,97,116,97,0,83,111,102,116, +66,111,100,121,76,105,110,107,68,97,116,97,0,83,111,102,116,66,111,100, +121,70,97,99,101,68,97,116,97,0,83,111,102,116,66,111,100,121,84,101, +116,114,97,68,97,116,97,0,83,111,102,116,82,105,103,105,100,65,110,99, +104,111,114,68,97,116,97,0,83,111,102,116,66,111,100,121,67,111,110,102, +105,103,68,97,116,97,0,83,111,102,116,66,111,100,121,80,111,115,101,68, +97,116,97,0,83,111,102,116,66,111,100,121,67,108,117,115,116,101,114,68, +97,116,97,0,98,116,83,111,102,116,66,111,100,121,74,111,105,110,116,68, +97,116,97,0,98,116,83,111,102,116,66,111,100,121,70,108,111,97,116,68, +97,116,97,0,84,76,69,78,1,0,1,0,2,0,2,0,4,0,4,0, +4,0,4,0,8,0,0,0,12,0,36,0,8,0,16,0,32,0,48,0, +96,0,64,0,-128,0,20,0,48,0,80,0,16,0,84,0,-124,0,12,0, +52,0,52,0,20,0,64,0,4,0,4,0,8,0,4,0,32,0,28,0, +60,0,56,0,76,0,76,0,24,0,60,0,60,0,16,0,64,0,68,0, +-56,1,-8,0,-32,1,-104,3,8,0,44,0,0,0,76,0,108,0,84,1, +-44,0,-52,0,-12,0,84,1,-60,0,16,0,100,0,20,0,36,0,100,0, +92,0,104,0,-64,0,92,1,104,0,-92,1,83,84,82,67,61,0,0,0, +10,0,3,0,4,0,0,0,4,0,1,0,9,0,2,0,11,0,3,0, +10,0,3,0,10,0,4,0,10,0,5,0,12,0,2,0,9,0,6,0, +9,0,7,0,13,0,1,0,7,0,8,0,14,0,1,0,8,0,8,0, +15,0,1,0,13,0,9,0,16,0,1,0,14,0,9,0,17,0,2,0, +15,0,10,0,13,0,11,0,18,0,2,0,16,0,10,0,14,0,11,0, +19,0,4,0,4,0,12,0,4,0,13,0,2,0,14,0,2,0,15,0, +20,0,6,0,13,0,16,0,13,0,17,0,4,0,18,0,4,0,19,0, +4,0,20,0,0,0,21,0,21,0,6,0,14,0,16,0,14,0,17,0, +4,0,18,0,4,0,19,0,4,0,20,0,0,0,21,0,22,0,3,0, +2,0,14,0,2,0,15,0,4,0,22,0,23,0,12,0,13,0,23,0, +13,0,24,0,13,0,25,0,4,0,26,0,4,0,27,0,4,0,28,0, +4,0,29,0,20,0,30,0,22,0,31,0,19,0,32,0,4,0,33,0, +4,0,34,0,24,0,12,0,14,0,23,0,14,0,24,0,14,0,25,0, +4,0,26,0,4,0,27,0,4,0,28,0,4,0,29,0,21,0,30,0, +22,0,31,0,4,0,33,0,4,0,34,0,19,0,32,0,25,0,3,0, +0,0,35,0,4,0,36,0,0,0,37,0,26,0,5,0,25,0,38,0, +13,0,39,0,13,0,40,0,7,0,41,0,0,0,21,0,27,0,5,0, +25,0,38,0,13,0,39,0,13,0,42,0,7,0,43,0,4,0,44,0, +28,0,2,0,13,0,45,0,7,0,46,0,29,0,4,0,27,0,47,0, +28,0,48,0,4,0,49,0,0,0,37,0,30,0,1,0,4,0,50,0, +31,0,2,0,2,0,50,0,0,0,51,0,32,0,2,0,2,0,52,0, +0,0,51,0,33,0,2,0,0,0,52,0,0,0,53,0,34,0,8,0, +13,0,54,0,14,0,55,0,30,0,56,0,32,0,57,0,33,0,58,0, +31,0,59,0,4,0,60,0,4,0,61,0,35,0,4,0,34,0,62,0, +13,0,63,0,4,0,64,0,0,0,37,0,36,0,7,0,25,0,38,0, +35,0,65,0,23,0,66,0,24,0,67,0,37,0,68,0,7,0,43,0, +0,0,69,0,38,0,2,0,36,0,70,0,13,0,39,0,39,0,4,0, +17,0,71,0,25,0,72,0,4,0,73,0,7,0,74,0,40,0,4,0, +25,0,38,0,39,0,75,0,4,0,76,0,7,0,43,0,41,0,3,0, +27,0,47,0,4,0,77,0,0,0,37,0,42,0,3,0,27,0,47,0, +4,0,77,0,0,0,37,0,43,0,4,0,4,0,78,0,7,0,79,0, +7,0,80,0,7,0,81,0,37,0,14,0,4,0,82,0,4,0,83,0, +43,0,84,0,4,0,85,0,7,0,86,0,7,0,87,0,7,0,88,0, +7,0,89,0,7,0,90,0,4,0,91,0,4,0,92,0,4,0,93,0, +4,0,94,0,0,0,37,0,44,0,5,0,25,0,38,0,35,0,65,0, +13,0,39,0,7,0,43,0,4,0,95,0,45,0,5,0,27,0,47,0, +13,0,96,0,14,0,97,0,4,0,98,0,0,0,99,0,46,0,24,0, +9,0,100,0,9,0,101,0,25,0,102,0,0,0,35,0,18,0,103,0, +18,0,104,0,14,0,105,0,14,0,106,0,14,0,107,0,8,0,108,0, +8,0,109,0,8,0,110,0,8,0,111,0,8,0,112,0,8,0,113,0, +8,0,114,0,4,0,115,0,4,0,116,0,4,0,117,0,4,0,118,0, +4,0,119,0,4,0,120,0,4,0,121,0,0,0,37,0,47,0,23,0, +9,0,100,0,9,0,101,0,25,0,102,0,0,0,35,0,17,0,103,0, +17,0,104,0,13,0,105,0,13,0,106,0,13,0,107,0,7,0,108,0, +7,0,109,0,7,0,110,0,7,0,111,0,7,0,112,0,7,0,113,0, +7,0,114,0,4,0,115,0,4,0,116,0,4,0,117,0,4,0,118,0, +4,0,119,0,4,0,120,0,4,0,121,0,48,0,21,0,47,0,122,0, +15,0,123,0,13,0,124,0,13,0,125,0,13,0,126,0,13,0,127,0, +13,0,-128,0,13,0,-127,0,13,0,-126,0,13,0,-125,0,13,0,-124,0, +7,0,-123,0,7,0,-122,0,7,0,-121,0,7,0,-120,0,7,0,-119,0, +7,0,-118,0,7,0,-117,0,7,0,-116,0,7,0,-115,0,4,0,-114,0, +49,0,22,0,46,0,122,0,16,0,123,0,14,0,124,0,14,0,125,0, +14,0,126,0,14,0,127,0,14,0,-128,0,14,0,-127,0,14,0,-126,0, +14,0,-125,0,14,0,-124,0,8,0,-123,0,8,0,-122,0,8,0,-121,0, +8,0,-120,0,8,0,-119,0,8,0,-118,0,8,0,-117,0,8,0,-116,0, +8,0,-115,0,4,0,-114,0,0,0,37,0,50,0,2,0,4,0,-113,0, +4,0,-112,0,51,0,11,0,52,0,-111,0,52,0,-110,0,0,0,35,0, +4,0,-109,0,4,0,-108,0,4,0,-107,0,4,0,-106,0,7,0,-105,0, +7,0,-104,0,4,0,-103,0,0,0,-102,0,53,0,3,0,51,0,-101,0, +13,0,-100,0,13,0,-99,0,54,0,3,0,51,0,-101,0,14,0,-100,0, +14,0,-99,0,55,0,13,0,51,0,-101,0,18,0,-98,0,18,0,-97,0, +4,0,-96,0,4,0,-95,0,4,0,-94,0,7,0,-93,0,7,0,-92,0, +7,0,-91,0,7,0,-90,0,7,0,-89,0,7,0,-88,0,7,0,-87,0, +56,0,13,0,51,0,-101,0,17,0,-98,0,17,0,-97,0,4,0,-96,0, +4,0,-95,0,4,0,-94,0,7,0,-93,0,7,0,-92,0,7,0,-91,0, +7,0,-90,0,7,0,-89,0,7,0,-88,0,7,0,-87,0,57,0,11,0, +51,0,-101,0,17,0,-98,0,17,0,-97,0,7,0,-86,0,7,0,-85,0, +7,0,-84,0,7,0,-89,0,7,0,-88,0,7,0,-87,0,7,0,-83,0, +0,0,21,0,58,0,9,0,51,0,-101,0,17,0,-98,0,17,0,-97,0, +13,0,-82,0,13,0,-81,0,13,0,-80,0,13,0,-79,0,4,0,-78,0, +4,0,-77,0,59,0,5,0,58,0,-76,0,4,0,-75,0,7,0,-74,0, +7,0,-73,0,7,0,-72,0,60,0,9,0,51,0,-101,0,17,0,-98,0, +17,0,-97,0,7,0,-82,0,7,0,-81,0,7,0,-80,0,7,0,-79,0, +4,0,-78,0,4,0,-77,0,61,0,4,0,7,0,-71,0,7,0,-70,0, +7,0,-69,0,4,0,78,0,62,0,10,0,61,0,-68,0,13,0,-67,0, +13,0,-66,0,13,0,-65,0,13,0,-64,0,13,0,-63,0,7,0,-123,0, +7,0,-62,0,4,0,-61,0,4,0,53,0,63,0,4,0,61,0,-68,0, +4,0,-60,0,7,0,-59,0,4,0,-58,0,64,0,4,0,13,0,-63,0, +61,0,-68,0,4,0,-57,0,7,0,-56,0,65,0,7,0,13,0,-55,0, +61,0,-68,0,4,0,-54,0,7,0,-53,0,7,0,-52,0,7,0,-51,0, +4,0,53,0,66,0,6,0,15,0,-50,0,13,0,-52,0,13,0,-49,0, +52,0,-48,0,4,0,-47,0,7,0,-51,0,67,0,26,0,4,0,-46,0, +7,0,-45,0,7,0,-83,0,7,0,-44,0,7,0,-43,0,7,0,-42,0, +7,0,-41,0,7,0,-40,0,7,0,-39,0,7,0,-38,0,7,0,-37,0, +7,0,-36,0,7,0,-35,0,7,0,-34,0,7,0,-33,0,7,0,-32,0, +7,0,-31,0,7,0,-30,0,7,0,-29,0,7,0,-28,0,7,0,-27,0, +4,0,-26,0,4,0,-25,0,4,0,-24,0,4,0,-23,0,4,0,116,0, +68,0,12,0,15,0,-22,0,15,0,-21,0,15,0,-20,0,13,0,-19,0, +13,0,-18,0,7,0,-17,0,4,0,-16,0,4,0,-15,0,4,0,-14,0, +4,0,-13,0,7,0,-53,0,4,0,53,0,69,0,27,0,17,0,-12,0, +15,0,-11,0,15,0,-10,0,13,0,-19,0,13,0,-9,0,13,0,-8,0, +13,0,-7,0,13,0,-6,0,13,0,-5,0,4,0,-4,0,7,0,-3,0, +4,0,-2,0,4,0,-1,0,4,0,0,1,7,0,1,1,7,0,2,1, +4,0,3,1,4,0,4,1,7,0,5,1,7,0,6,1,7,0,7,1, +7,0,8,1,7,0,9,1,7,0,10,1,4,0,11,1,4,0,12,1, +4,0,13,1,70,0,12,0,9,0,14,1,9,0,15,1,13,0,16,1, +7,0,17,1,7,0,18,1,7,0,19,1,4,0,20,1,13,0,21,1, +4,0,22,1,4,0,23,1,4,0,24,1,4,0,53,0,71,0,19,0, +47,0,122,0,68,0,25,1,61,0,26,1,62,0,27,1,63,0,28,1, +64,0,29,1,65,0,30,1,66,0,31,1,69,0,32,1,70,0,33,1, +4,0,34,1,4,0,-1,0,4,0,35,1,4,0,36,1,4,0,37,1, +4,0,38,1,4,0,39,1,4,0,40,1,67,0,41,1,}; +int sBulletDNAlen= sizeof(sBulletDNAstr); +unsigned char sBulletDNAstr64[]= { +83,68,78,65,78,65,77,69,42,1,0,0,109,95,115,105,122,101,0,109, +95,99,97,112,97,99,105,116,121,0,42,109,95,100,97,116,97,0,109,95, +99,111,108,108,105,115,105,111,110,83,104,97,112,101,115,0,109,95,99,111, +108,108,105,115,105,111,110,79,98,106,101,99,116,115,0,109,95,99,111,110, +115,116,114,97,105,110,116,115,0,42,102,105,114,115,116,0,42,108,97,115, +116,0,109,95,102,108,111,97,116,115,91,52,93,0,109,95,101,108,91,51, +93,0,109,95,98,97,115,105,115,0,109,95,111,114,105,103,105,110,0,109, +95,114,111,111,116,78,111,100,101,73,110,100,101,120,0,109,95,115,117,98, +116,114,101,101,83,105,122,101,0,109,95,113,117,97,110,116,105,122,101,100, +65,97,98,98,77,105,110,91,51,93,0,109,95,113,117,97,110,116,105,122, +101,100,65,97,98,98,77,97,120,91,51,93,0,109,95,97,97,98,98,77, +105,110,79,114,103,0,109,95,97,97,98,98,77,97,120,79,114,103,0,109, +95,101,115,99,97,112,101,73,110,100,101,120,0,109,95,115,117,98,80,97, +114,116,0,109,95,116,114,105,97,110,103,108,101,73,110,100,101,120,0,109, +95,112,97,100,91,52,93,0,109,95,101,115,99,97,112,101,73,110,100,101, +120,79,114,84,114,105,97,110,103,108,101,73,110,100,101,120,0,109,95,98, +118,104,65,97,98,98,77,105,110,0,109,95,98,118,104,65,97,98,98,77, +97,120,0,109,95,98,118,104,81,117,97,110,116,105,122,97,116,105,111,110, +0,109,95,99,117,114,78,111,100,101,73,110,100,101,120,0,109,95,117,115, +101,81,117,97,110,116,105,122,97,116,105,111,110,0,109,95,110,117,109,67, +111,110,116,105,103,117,111,117,115,76,101,97,102,78,111,100,101,115,0,109, +95,110,117,109,81,117,97,110,116,105,122,101,100,67,111,110,116,105,103,117, +111,117,115,78,111,100,101,115,0,42,109,95,99,111,110,116,105,103,117,111, +117,115,78,111,100,101,115,80,116,114,0,42,109,95,113,117,97,110,116,105, +122,101,100,67,111,110,116,105,103,117,111,117,115,78,111,100,101,115,80,116, +114,0,42,109,95,115,117,98,84,114,101,101,73,110,102,111,80,116,114,0, +109,95,116,114,97,118,101,114,115,97,108,77,111,100,101,0,109,95,110,117, +109,83,117,98,116,114,101,101,72,101,97,100,101,114,115,0,42,109,95,110, +97,109,101,0,109,95,115,104,97,112,101,84,121,112,101,0,109,95,112,97, +100,100,105,110,103,91,52,93,0,109,95,99,111,108,108,105,115,105,111,110, +83,104,97,112,101,68,97,116,97,0,109,95,108,111,99,97,108,83,99,97, +108,105,110,103,0,109,95,112,108,97,110,101,78,111,114,109,97,108,0,109, +95,112,108,97,110,101,67,111,110,115,116,97,110,116,0,109,95,105,109,112, +108,105,99,105,116,83,104,97,112,101,68,105,109,101,110,115,105,111,110,115, +0,109,95,99,111,108,108,105,115,105,111,110,77,97,114,103,105,110,0,109, +95,112,97,100,100,105,110,103,0,109,95,112,111,115,0,109,95,114,97,100, +105,117,115,0,109,95,99,111,110,118,101,120,73,110,116,101,114,110,97,108, +83,104,97,112,101,68,97,116,97,0,42,109,95,108,111,99,97,108,80,111, +115,105,116,105,111,110,65,114,114,97,121,80,116,114,0,109,95,108,111,99, +97,108,80,111,115,105,116,105,111,110,65,114,114,97,121,83,105,122,101,0, +109,95,118,97,108,117,101,0,109,95,112,97,100,91,50,93,0,109,95,118, +97,108,117,101,115,91,51,93,0,109,95,112,97,100,0,42,109,95,118,101, +114,116,105,99,101,115,51,102,0,42,109,95,118,101,114,116,105,99,101,115, +51,100,0,42,109,95,105,110,100,105,99,101,115,51,50,0,42,109,95,51, +105,110,100,105,99,101,115,49,54,0,42,109,95,51,105,110,100,105,99,101, +115,56,0,42,109,95,105,110,100,105,99,101,115,49,54,0,109,95,110,117, +109,84,114,105,97,110,103,108,101,115,0,109,95,110,117,109,86,101,114,116, +105,99,101,115,0,42,109,95,109,101,115,104,80,97,114,116,115,80,116,114, +0,109,95,115,99,97,108,105,110,103,0,109,95,110,117,109,77,101,115,104, +80,97,114,116,115,0,109,95,109,101,115,104,73,110,116,101,114,102,97,99, +101,0,42,109,95,113,117,97,110,116,105,122,101,100,70,108,111,97,116,66, +118,104,0,42,109,95,113,117,97,110,116,105,122,101,100,68,111,117,98,108, +101,66,118,104,0,42,109,95,116,114,105,97,110,103,108,101,73,110,102,111, +77,97,112,0,109,95,112,97,100,51,91,52,93,0,109,95,116,114,105,109, +101,115,104,83,104,97,112,101,68,97,116,97,0,109,95,116,114,97,110,115, +102,111,114,109,0,42,109,95,99,104,105,108,100,83,104,97,112,101,0,109, +95,99,104,105,108,100,83,104,97,112,101,84,121,112,101,0,109,95,99,104, +105,108,100,77,97,114,103,105,110,0,42,109,95,99,104,105,108,100,83,104, +97,112,101,80,116,114,0,109,95,110,117,109,67,104,105,108,100,83,104,97, +112,101,115,0,109,95,117,112,65,120,105,115,0,109,95,102,108,97,103,115, +0,109,95,101,100,103,101,86,48,86,49,65,110,103,108,101,0,109,95,101, +100,103,101,86,49,86,50,65,110,103,108,101,0,109,95,101,100,103,101,86, +50,86,48,65,110,103,108,101,0,42,109,95,104,97,115,104,84,97,98,108, +101,80,116,114,0,42,109,95,110,101,120,116,80,116,114,0,42,109,95,118, +97,108,117,101,65,114,114,97,121,80,116,114,0,42,109,95,107,101,121,65, +114,114,97,121,80,116,114,0,109,95,99,111,110,118,101,120,69,112,115,105, +108,111,110,0,109,95,112,108,97,110,97,114,69,112,115,105,108,111,110,0, +109,95,101,113,117,97,108,86,101,114,116,101,120,84,104,114,101,115,104,111, +108,100,0,109,95,101,100,103,101,68,105,115,116,97,110,99,101,84,104,114, +101,115,104,111,108,100,0,109,95,122,101,114,111,65,114,101,97,84,104,114, +101,115,104,111,108,100,0,109,95,110,101,120,116,83,105,122,101,0,109,95, +104,97,115,104,84,97,98,108,101,83,105,122,101,0,109,95,110,117,109,86, +97,108,117,101,115,0,109,95,110,117,109,75,101,121,115,0,109,95,103,105, +109,112,97,99,116,83,117,98,84,121,112,101,0,42,109,95,117,110,115,99, +97,108,101,100,80,111,105,110,116,115,70,108,111,97,116,80,116,114,0,42, +109,95,117,110,115,99,97,108,101,100,80,111,105,110,116,115,68,111,117,98, +108,101,80,116,114,0,109,95,110,117,109,85,110,115,99,97,108,101,100,80, +111,105,110,116,115,0,109,95,112,97,100,100,105,110,103,51,91,52,93,0, +42,109,95,98,114,111,97,100,112,104,97,115,101,72,97,110,100,108,101,0, +42,109,95,99,111,108,108,105,115,105,111,110,83,104,97,112,101,0,42,109, +95,114,111,111,116,67,111,108,108,105,115,105,111,110,83,104,97,112,101,0, +109,95,119,111,114,108,100,84,114,97,110,115,102,111,114,109,0,109,95,105, +110,116,101,114,112,111,108,97,116,105,111,110,87,111,114,108,100,84,114,97, +110,115,102,111,114,109,0,109,95,105,110,116,101,114,112,111,108,97,116,105, +111,110,76,105,110,101,97,114,86,101,108,111,99,105,116,121,0,109,95,105, +110,116,101,114,112,111,108,97,116,105,111,110,65,110,103,117,108,97,114,86, +101,108,111,99,105,116,121,0,109,95,97,110,105,115,111,116,114,111,112,105, +99,70,114,105,99,116,105,111,110,0,109,95,99,111,110,116,97,99,116,80, +114,111,99,101,115,115,105,110,103,84,104,114,101,115,104,111,108,100,0,109, +95,100,101,97,99,116,105,118,97,116,105,111,110,84,105,109,101,0,109,95, +102,114,105,99,116,105,111,110,0,109,95,114,101,115,116,105,116,117,116,105, +111,110,0,109,95,104,105,116,70,114,97,99,116,105,111,110,0,109,95,99, +99,100,83,119,101,112,116,83,112,104,101,114,101,82,97,100,105,117,115,0, +109,95,99,99,100,77,111,116,105,111,110,84,104,114,101,115,104,111,108,100, +0,109,95,104,97,115,65,110,105,115,111,116,114,111,112,105,99,70,114,105, +99,116,105,111,110,0,109,95,99,111,108,108,105,115,105,111,110,70,108,97, +103,115,0,109,95,105,115,108,97,110,100,84,97,103,49,0,109,95,99,111, +109,112,97,110,105,111,110,73,100,0,109,95,97,99,116,105,118,97,116,105, +111,110,83,116,97,116,101,49,0,109,95,105,110,116,101,114,110,97,108,84, +121,112,101,0,109,95,99,104,101,99,107,67,111,108,108,105,100,101,87,105, +116,104,0,109,95,99,111,108,108,105,115,105,111,110,79,98,106,101,99,116, +68,97,116,97,0,109,95,105,110,118,73,110,101,114,116,105,97,84,101,110, +115,111,114,87,111,114,108,100,0,109,95,108,105,110,101,97,114,86,101,108, +111,99,105,116,121,0,109,95,97,110,103,117,108,97,114,86,101,108,111,99, +105,116,121,0,109,95,97,110,103,117,108,97,114,70,97,99,116,111,114,0, +109,95,108,105,110,101,97,114,70,97,99,116,111,114,0,109,95,103,114,97, +118,105,116,121,0,109,95,103,114,97,118,105,116,121,95,97,99,99,101,108, +101,114,97,116,105,111,110,0,109,95,105,110,118,73,110,101,114,116,105,97, +76,111,99,97,108,0,109,95,116,111,116,97,108,70,111,114,99,101,0,109, +95,116,111,116,97,108,84,111,114,113,117,101,0,109,95,105,110,118,101,114, +115,101,77,97,115,115,0,109,95,108,105,110,101,97,114,68,97,109,112,105, +110,103,0,109,95,97,110,103,117,108,97,114,68,97,109,112,105,110,103,0, +109,95,97,100,100,105,116,105,111,110,97,108,68,97,109,112,105,110,103,70, +97,99,116,111,114,0,109,95,97,100,100,105,116,105,111,110,97,108,76,105, +110,101,97,114,68,97,109,112,105,110,103,84,104,114,101,115,104,111,108,100, +83,113,114,0,109,95,97,100,100,105,116,105,111,110,97,108,65,110,103,117, +108,97,114,68,97,109,112,105,110,103,84,104,114,101,115,104,111,108,100,83, +113,114,0,109,95,97,100,100,105,116,105,111,110,97,108,65,110,103,117,108, +97,114,68,97,109,112,105,110,103,70,97,99,116,111,114,0,109,95,108,105, +110,101,97,114,83,108,101,101,112,105,110,103,84,104,114,101,115,104,111,108, +100,0,109,95,97,110,103,117,108,97,114,83,108,101,101,112,105,110,103,84, +104,114,101,115,104,111,108,100,0,109,95,97,100,100,105,116,105,111,110,97, +108,68,97,109,112,105,110,103,0,109,95,110,117,109,67,111,110,115,116,114, +97,105,110,116,82,111,119,115,0,110,117,98,0,42,109,95,114,98,65,0, +42,109,95,114,98,66,0,109,95,111,98,106,101,99,116,84,121,112,101,0, +109,95,117,115,101,114,67,111,110,115,116,114,97,105,110,116,84,121,112,101, +0,109,95,117,115,101,114,67,111,110,115,116,114,97,105,110,116,73,100,0, +109,95,110,101,101,100,115,70,101,101,100,98,97,99,107,0,109,95,97,112, +112,108,105,101,100,73,109,112,117,108,115,101,0,109,95,100,98,103,68,114, +97,119,83,105,122,101,0,109,95,100,105,115,97,98,108,101,67,111,108,108, +105,115,105,111,110,115,66,101,116,119,101,101,110,76,105,110,107,101,100,66, +111,100,105,101,115,0,109,95,112,97,100,52,91,52,93,0,109,95,116,121, +112,101,67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,109,95,112, +105,118,111,116,73,110,65,0,109,95,112,105,118,111,116,73,110,66,0,109, +95,114,98,65,70,114,97,109,101,0,109,95,114,98,66,70,114,97,109,101, +0,109,95,117,115,101,82,101,102,101,114,101,110,99,101,70,114,97,109,101, +65,0,109,95,97,110,103,117,108,97,114,79,110,108,121,0,109,95,101,110, +97,98,108,101,65,110,103,117,108,97,114,77,111,116,111,114,0,109,95,109, +111,116,111,114,84,97,114,103,101,116,86,101,108,111,99,105,116,121,0,109, +95,109,97,120,77,111,116,111,114,73,109,112,117,108,115,101,0,109,95,108, +111,119,101,114,76,105,109,105,116,0,109,95,117,112,112,101,114,76,105,109, +105,116,0,109,95,108,105,109,105,116,83,111,102,116,110,101,115,115,0,109, +95,98,105,97,115,70,97,99,116,111,114,0,109,95,114,101,108,97,120,97, +116,105,111,110,70,97,99,116,111,114,0,109,95,115,119,105,110,103,83,112, +97,110,49,0,109,95,115,119,105,110,103,83,112,97,110,50,0,109,95,116, +119,105,115,116,83,112,97,110,0,109,95,100,97,109,112,105,110,103,0,109, +95,108,105,110,101,97,114,85,112,112,101,114,76,105,109,105,116,0,109,95, +108,105,110,101,97,114,76,111,119,101,114,76,105,109,105,116,0,109,95,97, +110,103,117,108,97,114,85,112,112,101,114,76,105,109,105,116,0,109,95,97, +110,103,117,108,97,114,76,111,119,101,114,76,105,109,105,116,0,109,95,117, +115,101,76,105,110,101,97,114,82,101,102,101,114,101,110,99,101,70,114,97, +109,101,65,0,109,95,117,115,101,79,102,102,115,101,116,70,111,114,67,111, +110,115,116,114,97,105,110,116,70,114,97,109,101,0,109,95,54,100,111,102, +68,97,116,97,0,109,95,115,112,114,105,110,103,69,110,97,98,108,101,100, +91,54,93,0,109,95,101,113,117,105,108,105,98,114,105,117,109,80,111,105, +110,116,91,54,93,0,109,95,115,112,114,105,110,103,83,116,105,102,102,110, +101,115,115,91,54,93,0,109,95,115,112,114,105,110,103,68,97,109,112,105, +110,103,91,54,93,0,109,95,108,105,110,101,97,114,83,116,105,102,102,110, +101,115,115,0,109,95,97,110,103,117,108,97,114,83,116,105,102,102,110,101, +115,115,0,109,95,118,111,108,117,109,101,83,116,105,102,102,110,101,115,115, +0,42,109,95,109,97,116,101,114,105,97,108,0,109,95,112,111,115,105,116, +105,111,110,0,109,95,112,114,101,118,105,111,117,115,80,111,115,105,116,105, +111,110,0,109,95,118,101,108,111,99,105,116,121,0,109,95,97,99,99,117, +109,117,108,97,116,101,100,70,111,114,99,101,0,109,95,110,111,114,109,97, +108,0,109,95,97,114,101,97,0,109,95,97,116,116,97,99,104,0,109,95, +110,111,100,101,73,110,100,105,99,101,115,91,50,93,0,109,95,114,101,115, +116,76,101,110,103,116,104,0,109,95,98,98,101,110,100,105,110,103,0,109, +95,110,111,100,101,73,110,100,105,99,101,115,91,51,93,0,109,95,114,101, +115,116,65,114,101,97,0,109,95,99,48,91,52,93,0,109,95,110,111,100, +101,73,110,100,105,99,101,115,91,52,93,0,109,95,114,101,115,116,86,111, +108,117,109,101,0,109,95,99,49,0,109,95,99,50,0,109,95,99,48,0, +109,95,108,111,99,97,108,70,114,97,109,101,0,42,109,95,114,105,103,105, +100,66,111,100,121,0,109,95,110,111,100,101,73,110,100,101,120,0,109,95, +97,101,114,111,77,111,100,101,108,0,109,95,98,97,117,109,103,97,114,116, +101,0,109,95,100,114,97,103,0,109,95,108,105,102,116,0,109,95,112,114, +101,115,115,117,114,101,0,109,95,118,111,108,117,109,101,0,109,95,100,121, +110,97,109,105,99,70,114,105,99,116,105,111,110,0,109,95,112,111,115,101, +77,97,116,99,104,0,109,95,114,105,103,105,100,67,111,110,116,97,99,116, +72,97,114,100,110,101,115,115,0,109,95,107,105,110,101,116,105,99,67,111, +110,116,97,99,116,72,97,114,100,110,101,115,115,0,109,95,115,111,102,116, +67,111,110,116,97,99,116,72,97,114,100,110,101,115,115,0,109,95,97,110, +99,104,111,114,72,97,114,100,110,101,115,115,0,109,95,115,111,102,116,82, +105,103,105,100,67,108,117,115,116,101,114,72,97,114,100,110,101,115,115,0, +109,95,115,111,102,116,75,105,110,101,116,105,99,67,108,117,115,116,101,114, +72,97,114,100,110,101,115,115,0,109,95,115,111,102,116,83,111,102,116,67, +108,117,115,116,101,114,72,97,114,100,110,101,115,115,0,109,95,115,111,102, +116,82,105,103,105,100,67,108,117,115,116,101,114,73,109,112,117,108,115,101, +83,112,108,105,116,0,109,95,115,111,102,116,75,105,110,101,116,105,99,67, +108,117,115,116,101,114,73,109,112,117,108,115,101,83,112,108,105,116,0,109, +95,115,111,102,116,83,111,102,116,67,108,117,115,116,101,114,73,109,112,117, +108,115,101,83,112,108,105,116,0,109,95,109,97,120,86,111,108,117,109,101, +0,109,95,116,105,109,101,83,99,97,108,101,0,109,95,118,101,108,111,99, +105,116,121,73,116,101,114,97,116,105,111,110,115,0,109,95,112,111,115,105, +116,105,111,110,73,116,101,114,97,116,105,111,110,115,0,109,95,100,114,105, +102,116,73,116,101,114,97,116,105,111,110,115,0,109,95,99,108,117,115,116, +101,114,73,116,101,114,97,116,105,111,110,115,0,109,95,114,111,116,0,109, +95,115,99,97,108,101,0,109,95,97,113,113,0,109,95,99,111,109,0,42, +109,95,112,111,115,105,116,105,111,110,115,0,42,109,95,119,101,105,103,104, +116,115,0,109,95,110,117,109,80,111,115,105,116,105,111,110,115,0,109,95, +110,117,109,87,101,105,103,116,115,0,109,95,98,118,111,108,117,109,101,0, +109,95,98,102,114,97,109,101,0,109,95,102,114,97,109,101,120,102,111,114, +109,0,109,95,108,111,99,105,105,0,109,95,105,110,118,119,105,0,109,95, +118,105,109,112,117,108,115,101,115,91,50,93,0,109,95,100,105,109,112,117, +108,115,101,115,91,50,93,0,109,95,108,118,0,109,95,97,118,0,42,109, +95,102,114,97,109,101,114,101,102,115,0,42,109,95,110,111,100,101,73,110, +100,105,99,101,115,0,42,109,95,109,97,115,115,101,115,0,109,95,110,117, +109,70,114,97,109,101,82,101,102,115,0,109,95,110,117,109,78,111,100,101, +115,0,109,95,110,117,109,77,97,115,115,101,115,0,109,95,105,100,109,97, +115,115,0,109,95,105,109,97,115,115,0,109,95,110,118,105,109,112,117,108, +115,101,115,0,109,95,110,100,105,109,112,117,108,115,101,115,0,109,95,110, +100,97,109,112,105,110,103,0,109,95,108,100,97,109,112,105,110,103,0,109, +95,97,100,97,109,112,105,110,103,0,109,95,109,97,116,99,104,105,110,103, +0,109,95,109,97,120,83,101,108,102,67,111,108,108,105,115,105,111,110,73, +109,112,117,108,115,101,0,109,95,115,101,108,102,67,111,108,108,105,115,105, +111,110,73,109,112,117,108,115,101,70,97,99,116,111,114,0,109,95,99,111, +110,116,97,105,110,115,65,110,99,104,111,114,0,109,95,99,111,108,108,105, +100,101,0,109,95,99,108,117,115,116,101,114,73,110,100,101,120,0,42,109, +95,98,111,100,121,65,0,42,109,95,98,111,100,121,66,0,109,95,114,101, +102,115,91,50,93,0,109,95,99,102,109,0,109,95,101,114,112,0,109,95, +115,112,108,105,116,0,109,95,100,101,108,101,116,101,0,109,95,114,101,108, +80,111,115,105,116,105,111,110,91,50,93,0,109,95,98,111,100,121,65,116, +121,112,101,0,109,95,98,111,100,121,66,116,121,112,101,0,109,95,106,111, +105,110,116,84,121,112,101,0,42,109,95,112,111,115,101,0,42,42,109,95, +109,97,116,101,114,105,97,108,115,0,42,109,95,110,111,100,101,115,0,42, +109,95,108,105,110,107,115,0,42,109,95,102,97,99,101,115,0,42,109,95, +116,101,116,114,97,104,101,100,114,97,0,42,109,95,97,110,99,104,111,114, +115,0,42,109,95,99,108,117,115,116,101,114,115,0,42,109,95,106,111,105, +110,116,115,0,109,95,110,117,109,77,97,116,101,114,105,97,108,115,0,109, +95,110,117,109,76,105,110,107,115,0,109,95,110,117,109,70,97,99,101,115, +0,109,95,110,117,109,84,101,116,114,97,104,101,100,114,97,0,109,95,110, +117,109,65,110,99,104,111,114,115,0,109,95,110,117,109,67,108,117,115,116, +101,114,115,0,109,95,110,117,109,74,111,105,110,116,115,0,109,95,99,111, +110,102,105,103,0,0,0,0,84,89,80,69,72,0,0,0,99,104,97,114, +0,117,99,104,97,114,0,115,104,111,114,116,0,117,115,104,111,114,116,0, +105,110,116,0,108,111,110,103,0,117,108,111,110,103,0,102,108,111,97,116, +0,100,111,117,98,108,101,0,118,111,105,100,0,80,111,105,110,116,101,114, +65,114,114,97,121,0,98,116,80,104,121,115,105,99,115,83,121,115,116,101, +109,0,76,105,115,116,66,97,115,101,0,98,116,86,101,99,116,111,114,51, +70,108,111,97,116,68,97,116,97,0,98,116,86,101,99,116,111,114,51,68, +111,117,98,108,101,68,97,116,97,0,98,116,77,97,116,114,105,120,51,120, +51,70,108,111,97,116,68,97,116,97,0,98,116,77,97,116,114,105,120,51, +120,51,68,111,117,98,108,101,68,97,116,97,0,98,116,84,114,97,110,115, +102,111,114,109,70,108,111,97,116,68,97,116,97,0,98,116,84,114,97,110, +115,102,111,114,109,68,111,117,98,108,101,68,97,116,97,0,98,116,66,118, +104,83,117,98,116,114,101,101,73,110,102,111,68,97,116,97,0,98,116,79, +112,116,105,109,105,122,101,100,66,118,104,78,111,100,101,70,108,111,97,116, +68,97,116,97,0,98,116,79,112,116,105,109,105,122,101,100,66,118,104,78, +111,100,101,68,111,117,98,108,101,68,97,116,97,0,98,116,81,117,97,110, +116,105,122,101,100,66,118,104,78,111,100,101,68,97,116,97,0,98,116,81, +117,97,110,116,105,122,101,100,66,118,104,70,108,111,97,116,68,97,116,97, +0,98,116,81,117,97,110,116,105,122,101,100,66,118,104,68,111,117,98,108, +101,68,97,116,97,0,98,116,67,111,108,108,105,115,105,111,110,83,104,97, +112,101,68,97,116,97,0,98,116,83,116,97,116,105,99,80,108,97,110,101, +83,104,97,112,101,68,97,116,97,0,98,116,67,111,110,118,101,120,73,110, +116,101,114,110,97,108,83,104,97,112,101,68,97,116,97,0,98,116,80,111, +115,105,116,105,111,110,65,110,100,82,97,100,105,117,115,0,98,116,77,117, +108,116,105,83,112,104,101,114,101,83,104,97,112,101,68,97,116,97,0,98, +116,73,110,116,73,110,100,101,120,68,97,116,97,0,98,116,83,104,111,114, +116,73,110,116,73,110,100,101,120,68,97,116,97,0,98,116,83,104,111,114, +116,73,110,116,73,110,100,101,120,84,114,105,112,108,101,116,68,97,116,97, +0,98,116,67,104,97,114,73,110,100,101,120,84,114,105,112,108,101,116,68, +97,116,97,0,98,116,77,101,115,104,80,97,114,116,68,97,116,97,0,98, +116,83,116,114,105,100,105,110,103,77,101,115,104,73,110,116,101,114,102,97, +99,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108,101,77,101,115, +104,83,104,97,112,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108, +101,73,110,102,111,77,97,112,68,97,116,97,0,98,116,83,99,97,108,101, +100,84,114,105,97,110,103,108,101,77,101,115,104,83,104,97,112,101,68,97, +116,97,0,98,116,67,111,109,112,111,117,110,100,83,104,97,112,101,67,104, +105,108,100,68,97,116,97,0,98,116,67,111,109,112,111,117,110,100,83,104, +97,112,101,68,97,116,97,0,98,116,67,121,108,105,110,100,101,114,83,104, +97,112,101,68,97,116,97,0,98,116,67,97,112,115,117,108,101,83,104,97, +112,101,68,97,116,97,0,98,116,84,114,105,97,110,103,108,101,73,110,102, +111,68,97,116,97,0,98,116,71,73,109,112,97,99,116,77,101,115,104,83, +104,97,112,101,68,97,116,97,0,98,116,67,111,110,118,101,120,72,117,108, +108,83,104,97,112,101,68,97,116,97,0,98,116,67,111,108,108,105,115,105, +111,110,79,98,106,101,99,116,68,111,117,98,108,101,68,97,116,97,0,98, +116,67,111,108,108,105,115,105,111,110,79,98,106,101,99,116,70,108,111,97, +116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121,70,108,111, +97,116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121,68,111, +117,98,108,101,68,97,116,97,0,98,116,67,111,110,115,116,114,97,105,110, +116,73,110,102,111,49,0,98,116,84,121,112,101,100,67,111,110,115,116,114, +97,105,110,116,68,97,116,97,0,98,116,82,105,103,105,100,66,111,100,121, +68,97,116,97,0,98,116,80,111,105,110,116,50,80,111,105,110,116,67,111, +110,115,116,114,97,105,110,116,70,108,111,97,116,68,97,116,97,0,98,116, +80,111,105,110,116,50,80,111,105,110,116,67,111,110,115,116,114,97,105,110, +116,68,111,117,98,108,101,68,97,116,97,0,98,116,72,105,110,103,101,67, +111,110,115,116,114,97,105,110,116,68,111,117,98,108,101,68,97,116,97,0, +98,116,72,105,110,103,101,67,111,110,115,116,114,97,105,110,116,70,108,111, +97,116,68,97,116,97,0,98,116,67,111,110,101,84,119,105,115,116,67,111, +110,115,116,114,97,105,110,116,68,97,116,97,0,98,116,71,101,110,101,114, +105,99,54,68,111,102,67,111,110,115,116,114,97,105,110,116,68,97,116,97, +0,98,116,71,101,110,101,114,105,99,54,68,111,102,83,112,114,105,110,103, +67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,98,116,83,108,105, +100,101,114,67,111,110,115,116,114,97,105,110,116,68,97,116,97,0,83,111, +102,116,66,111,100,121,77,97,116,101,114,105,97,108,68,97,116,97,0,83, +111,102,116,66,111,100,121,78,111,100,101,68,97,116,97,0,83,111,102,116, +66,111,100,121,76,105,110,107,68,97,116,97,0,83,111,102,116,66,111,100, +121,70,97,99,101,68,97,116,97,0,83,111,102,116,66,111,100,121,84,101, +116,114,97,68,97,116,97,0,83,111,102,116,82,105,103,105,100,65,110,99, +104,111,114,68,97,116,97,0,83,111,102,116,66,111,100,121,67,111,110,102, +105,103,68,97,116,97,0,83,111,102,116,66,111,100,121,80,111,115,101,68, +97,116,97,0,83,111,102,116,66,111,100,121,67,108,117,115,116,101,114,68, +97,116,97,0,98,116,83,111,102,116,66,111,100,121,74,111,105,110,116,68, +97,116,97,0,98,116,83,111,102,116,66,111,100,121,70,108,111,97,116,68, +97,116,97,0,84,76,69,78,1,0,1,0,2,0,2,0,4,0,4,0, +4,0,4,0,8,0,0,0,16,0,48,0,16,0,16,0,32,0,48,0, +96,0,64,0,-128,0,20,0,48,0,80,0,16,0,96,0,-112,0,16,0, +56,0,56,0,20,0,72,0,4,0,4,0,8,0,4,0,56,0,32,0, +80,0,72,0,96,0,80,0,32,0,64,0,64,0,16,0,72,0,80,0, +-40,1,8,1,-16,1,-88,3,8,0,56,0,0,0,88,0,120,0,96,1, +-32,0,-40,0,0,1,96,1,-48,0,16,0,104,0,24,0,40,0,104,0, +96,0,104,0,-56,0,104,1,112,0,-40,1,83,84,82,67,61,0,0,0, +10,0,3,0,4,0,0,0,4,0,1,0,9,0,2,0,11,0,3,0, +10,0,3,0,10,0,4,0,10,0,5,0,12,0,2,0,9,0,6,0, +9,0,7,0,13,0,1,0,7,0,8,0,14,0,1,0,8,0,8,0, +15,0,1,0,13,0,9,0,16,0,1,0,14,0,9,0,17,0,2,0, +15,0,10,0,13,0,11,0,18,0,2,0,16,0,10,0,14,0,11,0, +19,0,4,0,4,0,12,0,4,0,13,0,2,0,14,0,2,0,15,0, +20,0,6,0,13,0,16,0,13,0,17,0,4,0,18,0,4,0,19,0, +4,0,20,0,0,0,21,0,21,0,6,0,14,0,16,0,14,0,17,0, +4,0,18,0,4,0,19,0,4,0,20,0,0,0,21,0,22,0,3,0, +2,0,14,0,2,0,15,0,4,0,22,0,23,0,12,0,13,0,23,0, +13,0,24,0,13,0,25,0,4,0,26,0,4,0,27,0,4,0,28,0, +4,0,29,0,20,0,30,0,22,0,31,0,19,0,32,0,4,0,33,0, +4,0,34,0,24,0,12,0,14,0,23,0,14,0,24,0,14,0,25,0, +4,0,26,0,4,0,27,0,4,0,28,0,4,0,29,0,21,0,30,0, +22,0,31,0,4,0,33,0,4,0,34,0,19,0,32,0,25,0,3,0, +0,0,35,0,4,0,36,0,0,0,37,0,26,0,5,0,25,0,38,0, +13,0,39,0,13,0,40,0,7,0,41,0,0,0,21,0,27,0,5,0, +25,0,38,0,13,0,39,0,13,0,42,0,7,0,43,0,4,0,44,0, +28,0,2,0,13,0,45,0,7,0,46,0,29,0,4,0,27,0,47,0, +28,0,48,0,4,0,49,0,0,0,37,0,30,0,1,0,4,0,50,0, +31,0,2,0,2,0,50,0,0,0,51,0,32,0,2,0,2,0,52,0, +0,0,51,0,33,0,2,0,0,0,52,0,0,0,53,0,34,0,8,0, +13,0,54,0,14,0,55,0,30,0,56,0,32,0,57,0,33,0,58,0, +31,0,59,0,4,0,60,0,4,0,61,0,35,0,4,0,34,0,62,0, +13,0,63,0,4,0,64,0,0,0,37,0,36,0,7,0,25,0,38,0, +35,0,65,0,23,0,66,0,24,0,67,0,37,0,68,0,7,0,43,0, +0,0,69,0,38,0,2,0,36,0,70,0,13,0,39,0,39,0,4,0, +17,0,71,0,25,0,72,0,4,0,73,0,7,0,74,0,40,0,4,0, +25,0,38,0,39,0,75,0,4,0,76,0,7,0,43,0,41,0,3,0, +27,0,47,0,4,0,77,0,0,0,37,0,42,0,3,0,27,0,47,0, +4,0,77,0,0,0,37,0,43,0,4,0,4,0,78,0,7,0,79,0, +7,0,80,0,7,0,81,0,37,0,14,0,4,0,82,0,4,0,83,0, +43,0,84,0,4,0,85,0,7,0,86,0,7,0,87,0,7,0,88,0, +7,0,89,0,7,0,90,0,4,0,91,0,4,0,92,0,4,0,93,0, +4,0,94,0,0,0,37,0,44,0,5,0,25,0,38,0,35,0,65,0, +13,0,39,0,7,0,43,0,4,0,95,0,45,0,5,0,27,0,47,0, +13,0,96,0,14,0,97,0,4,0,98,0,0,0,99,0,46,0,24,0, +9,0,100,0,9,0,101,0,25,0,102,0,0,0,35,0,18,0,103,0, +18,0,104,0,14,0,105,0,14,0,106,0,14,0,107,0,8,0,108,0, +8,0,109,0,8,0,110,0,8,0,111,0,8,0,112,0,8,0,113,0, +8,0,114,0,4,0,115,0,4,0,116,0,4,0,117,0,4,0,118,0, +4,0,119,0,4,0,120,0,4,0,121,0,0,0,37,0,47,0,23,0, +9,0,100,0,9,0,101,0,25,0,102,0,0,0,35,0,17,0,103,0, +17,0,104,0,13,0,105,0,13,0,106,0,13,0,107,0,7,0,108,0, +7,0,109,0,7,0,110,0,7,0,111,0,7,0,112,0,7,0,113,0, +7,0,114,0,4,0,115,0,4,0,116,0,4,0,117,0,4,0,118,0, +4,0,119,0,4,0,120,0,4,0,121,0,48,0,21,0,47,0,122,0, +15,0,123,0,13,0,124,0,13,0,125,0,13,0,126,0,13,0,127,0, +13,0,-128,0,13,0,-127,0,13,0,-126,0,13,0,-125,0,13,0,-124,0, +7,0,-123,0,7,0,-122,0,7,0,-121,0,7,0,-120,0,7,0,-119,0, +7,0,-118,0,7,0,-117,0,7,0,-116,0,7,0,-115,0,4,0,-114,0, +49,0,22,0,46,0,122,0,16,0,123,0,14,0,124,0,14,0,125,0, +14,0,126,0,14,0,127,0,14,0,-128,0,14,0,-127,0,14,0,-126,0, +14,0,-125,0,14,0,-124,0,8,0,-123,0,8,0,-122,0,8,0,-121,0, +8,0,-120,0,8,0,-119,0,8,0,-118,0,8,0,-117,0,8,0,-116,0, +8,0,-115,0,4,0,-114,0,0,0,37,0,50,0,2,0,4,0,-113,0, +4,0,-112,0,51,0,11,0,52,0,-111,0,52,0,-110,0,0,0,35,0, +4,0,-109,0,4,0,-108,0,4,0,-107,0,4,0,-106,0,7,0,-105,0, +7,0,-104,0,4,0,-103,0,0,0,-102,0,53,0,3,0,51,0,-101,0, +13,0,-100,0,13,0,-99,0,54,0,3,0,51,0,-101,0,14,0,-100,0, +14,0,-99,0,55,0,13,0,51,0,-101,0,18,0,-98,0,18,0,-97,0, +4,0,-96,0,4,0,-95,0,4,0,-94,0,7,0,-93,0,7,0,-92,0, +7,0,-91,0,7,0,-90,0,7,0,-89,0,7,0,-88,0,7,0,-87,0, +56,0,13,0,51,0,-101,0,17,0,-98,0,17,0,-97,0,4,0,-96,0, +4,0,-95,0,4,0,-94,0,7,0,-93,0,7,0,-92,0,7,0,-91,0, +7,0,-90,0,7,0,-89,0,7,0,-88,0,7,0,-87,0,57,0,11,0, +51,0,-101,0,17,0,-98,0,17,0,-97,0,7,0,-86,0,7,0,-85,0, +7,0,-84,0,7,0,-89,0,7,0,-88,0,7,0,-87,0,7,0,-83,0, +0,0,21,0,58,0,9,0,51,0,-101,0,17,0,-98,0,17,0,-97,0, +13,0,-82,0,13,0,-81,0,13,0,-80,0,13,0,-79,0,4,0,-78,0, +4,0,-77,0,59,0,5,0,58,0,-76,0,4,0,-75,0,7,0,-74,0, +7,0,-73,0,7,0,-72,0,60,0,9,0,51,0,-101,0,17,0,-98,0, +17,0,-97,0,7,0,-82,0,7,0,-81,0,7,0,-80,0,7,0,-79,0, +4,0,-78,0,4,0,-77,0,61,0,4,0,7,0,-71,0,7,0,-70,0, +7,0,-69,0,4,0,78,0,62,0,10,0,61,0,-68,0,13,0,-67,0, +13,0,-66,0,13,0,-65,0,13,0,-64,0,13,0,-63,0,7,0,-123,0, +7,0,-62,0,4,0,-61,0,4,0,53,0,63,0,4,0,61,0,-68,0, +4,0,-60,0,7,0,-59,0,4,0,-58,0,64,0,4,0,13,0,-63,0, +61,0,-68,0,4,0,-57,0,7,0,-56,0,65,0,7,0,13,0,-55,0, +61,0,-68,0,4,0,-54,0,7,0,-53,0,7,0,-52,0,7,0,-51,0, +4,0,53,0,66,0,6,0,15,0,-50,0,13,0,-52,0,13,0,-49,0, +52,0,-48,0,4,0,-47,0,7,0,-51,0,67,0,26,0,4,0,-46,0, +7,0,-45,0,7,0,-83,0,7,0,-44,0,7,0,-43,0,7,0,-42,0, +7,0,-41,0,7,0,-40,0,7,0,-39,0,7,0,-38,0,7,0,-37,0, +7,0,-36,0,7,0,-35,0,7,0,-34,0,7,0,-33,0,7,0,-32,0, +7,0,-31,0,7,0,-30,0,7,0,-29,0,7,0,-28,0,7,0,-27,0, +4,0,-26,0,4,0,-25,0,4,0,-24,0,4,0,-23,0,4,0,116,0, +68,0,12,0,15,0,-22,0,15,0,-21,0,15,0,-20,0,13,0,-19,0, +13,0,-18,0,7,0,-17,0,4,0,-16,0,4,0,-15,0,4,0,-14,0, +4,0,-13,0,7,0,-53,0,4,0,53,0,69,0,27,0,17,0,-12,0, +15,0,-11,0,15,0,-10,0,13,0,-19,0,13,0,-9,0,13,0,-8,0, +13,0,-7,0,13,0,-6,0,13,0,-5,0,4,0,-4,0,7,0,-3,0, +4,0,-2,0,4,0,-1,0,4,0,0,1,7,0,1,1,7,0,2,1, +4,0,3,1,4,0,4,1,7,0,5,1,7,0,6,1,7,0,7,1, +7,0,8,1,7,0,9,1,7,0,10,1,4,0,11,1,4,0,12,1, +4,0,13,1,70,0,12,0,9,0,14,1,9,0,15,1,13,0,16,1, +7,0,17,1,7,0,18,1,7,0,19,1,4,0,20,1,13,0,21,1, +4,0,22,1,4,0,23,1,4,0,24,1,4,0,53,0,71,0,19,0, +47,0,122,0,68,0,25,1,61,0,26,1,62,0,27,1,63,0,28,1, +64,0,29,1,65,0,30,1,66,0,31,1,69,0,32,1,70,0,33,1, +4,0,34,1,4,0,-1,0,4,0,35,1,4,0,36,1,4,0,37,1, +4,0,38,1,4,0,39,1,4,0,40,1,67,0,41,1,}; +int sBulletDNAlen64= sizeof(sBulletDNAstr64); diff --git a/extern/bullet2/src/LinearMath/btSerializer.h b/extern/bullet2/src/LinearMath/btSerializer.h new file mode 100644 index 00000000000..8a89374c612 --- /dev/null +++ b/extern/bullet2/src/LinearMath/btSerializer.h @@ -0,0 +1,655 @@ +/* +Bullet Continuous Collision Detection and Physics Library +Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org + +This software is provided 'as-is', without any express or implied warranty. +In no event will the authors be held liable for any damages arising from the use of this software. +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it freely, +subject to the following restrictions: + +1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. +*/ + +#ifndef BT_SERIALIZER_H +#define BT_SERIALIZER_H + +#include "btScalar.h" // has definitions like SIMD_FORCE_INLINE +#include "btStackAlloc.h" +#include "btHashMap.h" + +#if !defined( __CELLOS_LV2__) && !defined(__MWERKS__) +#include <memory.h> +#endif +#include <string.h> + + + +///only the 32bit versions for now +extern unsigned char sBulletDNAstr[]; +extern int sBulletDNAlen; +extern unsigned char sBulletDNAstr64[]; +extern int sBulletDNAlen64; + +SIMD_FORCE_INLINE int btStrLen(const char* str) +{ + if (!str) + return(0); + int len = 0; + + while (*str != 0) + { + str++; + len++; + } + + return len; +} + + +class btChunk +{ +public: + int m_chunkCode; + int m_length; + void *m_oldPtr; + int m_dna_nr; + int m_number; +}; + +enum btSerializationFlags +{ + BT_SERIALIZE_NO_BVH = 1, + BT_SERIALIZE_NO_TRIANGLEINFOMAP = 2, + BT_SERIALIZE_NO_DUPLICATE_ASSERT = 4 +}; + +class btSerializer +{ + +public: + + virtual ~btSerializer() {} + + virtual const unsigned char* getBufferPointer() const = 0; + + virtual int getCurrentBufferSize() const = 0; + + virtual btChunk* allocate(size_t size, int numElements) = 0; + + virtual void finalizeChunk(btChunk* chunk, const char* structType, int chunkCode,void* oldPtr)= 0; + + virtual void* findPointer(void* oldPtr) = 0; + + virtual void* getUniquePointer(void*oldPtr) = 0; + + virtual void startSerialization() = 0; + + virtual void finishSerialization() = 0; + + virtual const char* findNameForPointer(const void* ptr) const = 0; + + virtual void registerNameForPointer(const void* ptr, const char* name) = 0; + + virtual void serializeName(const char* ptr) = 0; + + virtual int getSerializationFlags() const = 0; + + virtual void setSerializationFlags(int flags) = 0; + + +}; + + + +#define BT_HEADER_LENGTH 12 +#if defined(__sgi) || defined (__sparc) || defined (__sparc__) || defined (__PPC__) || defined (__ppc__) || defined (__BIG_ENDIAN__) +# define MAKE_ID(a,b,c,d) ( (int)(a)<<24 | (int)(b)<<16 | (c)<<8 | (d) ) +#else +# define MAKE_ID(a,b,c,d) ( (int)(d)<<24 | (int)(c)<<16 | (b)<<8 | (a) ) +#endif + +#define BT_SOFTBODY_CODE MAKE_ID('S','B','D','Y') +#define BT_COLLISIONOBJECT_CODE MAKE_ID('C','O','B','J') +#define BT_RIGIDBODY_CODE MAKE_ID('R','B','D','Y') +#define BT_CONSTRAINT_CODE MAKE_ID('C','O','N','S') +#define BT_BOXSHAPE_CODE MAKE_ID('B','O','X','S') +#define BT_QUANTIZED_BVH_CODE MAKE_ID('Q','B','V','H') +#define BT_TRIANLGE_INFO_MAP MAKE_ID('T','M','A','P') +#define BT_SHAPE_CODE MAKE_ID('S','H','A','P') +#define BT_ARRAY_CODE MAKE_ID('A','R','A','Y') +#define BT_SBMATERIAL_CODE MAKE_ID('S','B','M','T') +#define BT_SBNODE_CODE MAKE_ID('S','B','N','D') +#define BT_DNA_CODE MAKE_ID('D','N','A','1') + + +struct btPointerUid +{ + union + { + void* m_ptr; + int m_uniqueIds[2]; + }; +}; + +///The btDefaultSerializer is the main Bullet serialization class. +///The constructor takes an optional argument for backwards compatibility, it is recommended to leave this empty/zero. +class btDefaultSerializer : public btSerializer +{ + + + btAlignedObjectArray<char*> mTypes; + btAlignedObjectArray<short*> mStructs; + btAlignedObjectArray<short> mTlens; + btHashMap<btHashInt, int> mStructReverse; + btHashMap<btHashString,int> mTypeLookup; + + + btHashMap<btHashPtr,void*> m_chunkP; + + btHashMap<btHashPtr,const char*> m_nameMap; + + btHashMap<btHashPtr,btPointerUid> m_uniquePointers; + int m_uniqueIdGenerator; + + int m_totalSize; + unsigned char* m_buffer; + int m_currentSize; + void* m_dna; + int m_dnaLength; + + int m_serializationFlags; + + + btAlignedObjectArray<btChunk*> m_chunkPtrs; + +protected: + + virtual void* findPointer(void* oldPtr) + { + void** ptr = m_chunkP.find(oldPtr); + if (ptr && *ptr) + return *ptr; + return 0; + } + + + + + + void writeDNA() + { + btChunk* dnaChunk = allocate(m_dnaLength,1); + memcpy(dnaChunk->m_oldPtr,m_dna,m_dnaLength); + finalizeChunk(dnaChunk,"DNA1",BT_DNA_CODE, m_dna); + } + + int getReverseType(const char *type) const + { + + btHashString key(type); + const int* valuePtr = mTypeLookup.find(key); + if (valuePtr) + return *valuePtr; + + return -1; + } + + void initDNA(const char* bdnaOrg,int dnalen) + { + ///was already initialized + if (m_dna) + return; + + int littleEndian= 1; + littleEndian= ((char*)&littleEndian)[0]; + + + m_dna = btAlignedAlloc(dnalen,16); + memcpy(m_dna,bdnaOrg,dnalen); + m_dnaLength = dnalen; + + int *intPtr=0; + short *shtPtr=0; + char *cp = 0;int dataLen =0;long nr=0; + intPtr = (int*)m_dna; + + /* + SDNA (4 bytes) (magic number) + NAME (4 bytes) + <nr> (4 bytes) amount of names (int) + <string> + <string> + */ + + if (strncmp((const char*)m_dna, "SDNA", 4)==0) + { + // skip ++ NAME + intPtr++; intPtr++; + } + + // Parse names + if (!littleEndian) + *intPtr = btSwapEndian(*intPtr); + + dataLen = *intPtr; + + intPtr++; + + cp = (char*)intPtr; + int i; + for ( i=0; i<dataLen; i++) + { + + while (*cp)cp++; + cp++; + } + { + nr= (long)cp; + // long mask=3; + nr= ((nr+3)&~3)-nr; + while (nr--) + { + cp++; + } + } + + /* + TYPE (4 bytes) + <nr> amount of types (int) + <string> + <string> + */ + + intPtr = (int*)cp; + assert(strncmp(cp, "TYPE", 4)==0); intPtr++; + + if (!littleEndian) + *intPtr = btSwapEndian(*intPtr); + + dataLen = *intPtr; + intPtr++; + + + cp = (char*)intPtr; + for (i=0; i<dataLen; i++) + { + mTypes.push_back(cp); + while (*cp)cp++; + cp++; + } + + { + nr= (long)cp; + // long mask=3; + nr= ((nr+3)&~3)-nr; + while (nr--) + { + cp++; + } + } + + + /* + TLEN (4 bytes) + <len> (short) the lengths of types + <len> + */ + + // Parse type lens + intPtr = (int*)cp; + assert(strncmp(cp, "TLEN", 4)==0); intPtr++; + + dataLen = (int)mTypes.size(); + + shtPtr = (short*)intPtr; + for (i=0; i<dataLen; i++, shtPtr++) + { + if (!littleEndian) + shtPtr[0] = btSwapEndian(shtPtr[0]); + mTlens.push_back(shtPtr[0]); + } + + if (dataLen & 1) shtPtr++; + + /* + STRC (4 bytes) + <nr> amount of structs (int) + <typenr> + <nr_of_elems> + <typenr> + <namenr> + <typenr> + <namenr> + */ + + intPtr = (int*)shtPtr; + cp = (char*)intPtr; + assert(strncmp(cp, "STRC", 4)==0); intPtr++; + + if (!littleEndian) + *intPtr = btSwapEndian(*intPtr); + dataLen = *intPtr ; + intPtr++; + + + shtPtr = (short*)intPtr; + for (i=0; i<dataLen; i++) + { + mStructs.push_back (shtPtr); + + if (!littleEndian) + { + shtPtr[0]= btSwapEndian(shtPtr[0]); + shtPtr[1]= btSwapEndian(shtPtr[1]); + + int len = shtPtr[1]; + shtPtr+= 2; + + for (int a=0; a<len; a++, shtPtr+=2) + { + shtPtr[0]= btSwapEndian(shtPtr[0]); + shtPtr[1]= btSwapEndian(shtPtr[1]); + } + + } else + { + shtPtr+= (2*shtPtr[1])+2; + } + } + + // build reverse lookups + for (i=0; i<(int)mStructs.size(); i++) + { + short *strc = mStructs.at(i); + mStructReverse.insert(strc[0], i); + mTypeLookup.insert(btHashString(mTypes[strc[0]]),i); + } + } + +public: + + + + + btDefaultSerializer(int totalSize=0) + :m_totalSize(totalSize), + m_currentSize(0), + m_dna(0), + m_dnaLength(0), + m_serializationFlags(0) + { + m_buffer = m_totalSize?(unsigned char*)btAlignedAlloc(totalSize,16):0; + + const bool VOID_IS_8 = ((sizeof(void*)==8)); + +#ifdef BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES + if (VOID_IS_8) + { +#if _WIN64 + initDNA((const char*)sBulletDNAstr64,sBulletDNAlen64); +#else + btAssert(0); +#endif + } else + { +#ifndef _WIN64 + initDNA((const char*)sBulletDNAstr,sBulletDNAlen); +#else + btAssert(0); +#endif + } + +#else //BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES + if (VOID_IS_8) + { + initDNA((const char*)sBulletDNAstr64,sBulletDNAlen64); + } else + { + initDNA((const char*)sBulletDNAstr,sBulletDNAlen); + } +#endif //BT_INTERNAL_UPDATE_SERIALIZATION_STRUCTURES + + } + + virtual ~btDefaultSerializer() + { + if (m_buffer) + btAlignedFree(m_buffer); + if (m_dna) + btAlignedFree(m_dna); + } + + void writeHeader(unsigned char* buffer) const + { + + +#ifdef BT_USE_DOUBLE_PRECISION + memcpy(buffer, "BULLETd", 7); +#else + memcpy(buffer, "BULLETf", 7); +#endif //BT_USE_DOUBLE_PRECISION + + int littleEndian= 1; + littleEndian= ((char*)&littleEndian)[0]; + + if (sizeof(void*)==8) + { + buffer[7] = '-'; + } else + { + buffer[7] = '_'; + } + + if (littleEndian) + { + buffer[8]='v'; + } else + { + buffer[8]='V'; + } + + + buffer[9] = '2'; + buffer[10] = '7'; + buffer[11] = '8'; + + } + + virtual void startSerialization() + { + m_uniqueIdGenerator= 1; + if (m_totalSize) + { + unsigned char* buffer = internalAlloc(BT_HEADER_LENGTH); + writeHeader(buffer); + } + + } + + virtual void finishSerialization() + { + writeDNA(); + + //if we didn't pre-allocate a buffer, we need to create a contiguous buffer now + int mysize = 0; + if (!m_totalSize) + { + if (m_buffer) + btAlignedFree(m_buffer); + + m_currentSize += BT_HEADER_LENGTH; + m_buffer = (unsigned char*)btAlignedAlloc(m_currentSize,16); + + unsigned char* currentPtr = m_buffer; + writeHeader(m_buffer); + currentPtr += BT_HEADER_LENGTH; + mysize+=BT_HEADER_LENGTH; + for (int i=0;i< m_chunkPtrs.size();i++) + { + int curLength = sizeof(btChunk)+m_chunkPtrs[i]->m_length; + memcpy(currentPtr,m_chunkPtrs[i], curLength); + btAlignedFree(m_chunkPtrs[i]); + currentPtr+=curLength; + mysize+=curLength; + } + } + + mTypes.clear(); + mStructs.clear(); + mTlens.clear(); + mStructReverse.clear(); + mTypeLookup.clear(); + m_chunkP.clear(); + m_nameMap.clear(); + m_uniquePointers.clear(); + m_chunkPtrs.clear(); + } + + virtual void* getUniquePointer(void*oldPtr) + { + if (!oldPtr) + return 0; + + btPointerUid* uptr = (btPointerUid*)m_uniquePointers.find(oldPtr); + if (uptr) + { + return uptr->m_ptr; + } + m_uniqueIdGenerator++; + + btPointerUid uid; + uid.m_uniqueIds[0] = m_uniqueIdGenerator; + uid.m_uniqueIds[1] = m_uniqueIdGenerator; + m_uniquePointers.insert(oldPtr,uid); + return uid.m_ptr; + + } + + virtual const unsigned char* getBufferPointer() const + { + return m_buffer; + } + + virtual int getCurrentBufferSize() const + { + return m_currentSize; + } + + virtual void finalizeChunk(btChunk* chunk, const char* structType, int chunkCode,void* oldPtr) + { + if (!(m_serializationFlags&BT_SERIALIZE_NO_DUPLICATE_ASSERT)) + { + btAssert(!findPointer(oldPtr)); + } + + chunk->m_dna_nr = getReverseType(structType); + + chunk->m_chunkCode = chunkCode; + + void* uniquePtr = getUniquePointer(oldPtr); + + m_chunkP.insert(oldPtr,uniquePtr);//chunk->m_oldPtr); + chunk->m_oldPtr = uniquePtr;//oldPtr; + + } + + + virtual unsigned char* internalAlloc(size_t size) + { + unsigned char* ptr = 0; + + if (m_totalSize) + { + ptr = m_buffer+m_currentSize; + m_currentSize += int(size); + btAssert(m_currentSize<m_totalSize); + } else + { + ptr = (unsigned char*)btAlignedAlloc(size,16); + m_currentSize += int(size); + } + return ptr; + } + + + + virtual btChunk* allocate(size_t size, int numElements) + { + + unsigned char* ptr = internalAlloc(int(size)*numElements+sizeof(btChunk)); + + unsigned char* data = ptr + sizeof(btChunk); + + btChunk* chunk = (btChunk*)ptr; + chunk->m_chunkCode = 0; + chunk->m_oldPtr = data; + chunk->m_length = int(size)*numElements; + chunk->m_number = numElements; + + m_chunkPtrs.push_back(chunk); + + + return chunk; + } + + virtual const char* findNameForPointer(const void* ptr) const + { + const char*const * namePtr = m_nameMap.find(ptr); + if (namePtr && *namePtr) + return *namePtr; + return 0; + + } + + virtual void registerNameForPointer(const void* ptr, const char* name) + { + m_nameMap.insert(ptr,name); + } + + virtual void serializeName(const char* name) + { + if (name) + { + //don't serialize name twice + if (findPointer((void*)name)) + return; + + int len = btStrLen(name); + if (len) + { + + int newLen = len+1; + int padding = ((newLen+3)&~3)-newLen; + newLen += padding; + + //serialize name string now + btChunk* chunk = allocate(sizeof(char),newLen); + char* destinationName = (char*)chunk->m_oldPtr; + for (int i=0;i<len;i++) + { + destinationName[i] = name[i]; + } + destinationName[len] = 0; + finalizeChunk(chunk,"char",BT_ARRAY_CODE,(void*)name); + } + } + } + + virtual int getSerializationFlags() const + { + return m_serializationFlags; + } + + virtual void setSerializationFlags(int flags) + { + m_serializationFlags = flags; + } + +}; + + +#endif //BT_SERIALIZER_H + diff --git a/extern/bullet2/src/LinearMath/btTransform.h b/extern/bullet2/src/LinearMath/btTransform.h index c4fe33eecd7..187b09116cc 100644 --- a/extern/bullet2/src/LinearMath/btTransform.h +++ b/extern/bullet2/src/LinearMath/btTransform.h @@ -17,14 +17,26 @@ subject to the following restrictions: #ifndef btTransform_H #define btTransform_H -#include "btVector3.h" + #include "btMatrix3x3.h" +#ifdef BT_USE_DOUBLE_PRECISION +#define btTransformData btTransformDoubleData +#else +#define btTransformData btTransformFloatData +#endif + + + /**@brief The btTransform class supports rigid transforms with only translation and rotation and no scaling/shear. *It can be used in combination with btVector3, btQuaternion and btMatrix3x3 linear algebra classes. */ class btTransform { + ///Storage for the rotation + btMatrix3x3 m_basis; + ///Storage for the translation + btVector3 m_origin; public: @@ -195,12 +207,17 @@ public: static const btTransform identityTransform(btMatrix3x3::getIdentity()); return identityTransform; } - -private: - ///Storage for the rotation - btMatrix3x3 m_basis; - ///Storage for the translation - btVector3 m_origin; + + void serialize(struct btTransformData& dataOut) const; + + void serializeFloat(struct btTransformFloatData& dataOut) const; + + void deSerialize(const struct btTransformData& dataIn); + + void deSerializeDouble(const struct btTransformDoubleData& dataIn); + + void deSerializeFloat(const struct btTransformFloatData& dataIn); + }; @@ -234,6 +251,53 @@ SIMD_FORCE_INLINE bool operator==(const btTransform& t1, const btTransform& t2) } +///for serialization +struct btTransformFloatData +{ + btMatrix3x3FloatData m_basis; + btVector3FloatData m_origin; +}; + +struct btTransformDoubleData +{ + btMatrix3x3DoubleData m_basis; + btVector3DoubleData m_origin; +}; + + + +SIMD_FORCE_INLINE void btTransform::serialize(btTransformData& dataOut) const +{ + m_basis.serialize(dataOut.m_basis); + m_origin.serialize(dataOut.m_origin); +} + +SIMD_FORCE_INLINE void btTransform::serializeFloat(btTransformFloatData& dataOut) const +{ + m_basis.serializeFloat(dataOut.m_basis); + m_origin.serializeFloat(dataOut.m_origin); +} + + +SIMD_FORCE_INLINE void btTransform::deSerialize(const btTransformData& dataIn) +{ + m_basis.deSerialize(dataIn.m_basis); + m_origin.deSerialize(dataIn.m_origin); +} + +SIMD_FORCE_INLINE void btTransform::deSerializeFloat(const btTransformFloatData& dataIn) +{ + m_basis.deSerializeFloat(dataIn.m_basis); + m_origin.deSerializeFloat(dataIn.m_origin); +} + +SIMD_FORCE_INLINE void btTransform::deSerializeDouble(const btTransformDoubleData& dataIn) +{ + m_basis.deSerializeDouble(dataIn.m_basis); + m_origin.deSerializeDouble(dataIn.m_origin); +} + + #endif diff --git a/extern/bullet2/src/LinearMath/btTransformUtil.h b/extern/bullet2/src/LinearMath/btTransformUtil.h index e8328da4ca6..626110ce4ee 100644 --- a/extern/bullet2/src/LinearMath/btTransformUtil.h +++ b/extern/bullet2/src/LinearMath/btTransformUtil.h @@ -21,9 +21,6 @@ subject to the following restrictions: -#define SIMDSQRT12 btScalar(0.7071067811865475244008443621048490) - -#define btRecipSqrt(x) ((btScalar)(btScalar(1.0)/btSqrt(btScalar(x)))) /* reciprocal square root */ SIMD_FORCE_INLINE btVector3 btAabbSupport(const btVector3& halfExtents,const btVector3& supportDir) { @@ -33,25 +30,7 @@ SIMD_FORCE_INLINE btVector3 btAabbSupport(const btVector3& halfExtents,const btV } -SIMD_FORCE_INLINE void btPlaneSpace1 (const btVector3& n, btVector3& p, btVector3& q) -{ - if (btFabs(n.z()) > SIMDSQRT12) { - // choose p in y-z plane - btScalar a = n[1]*n[1] + n[2]*n[2]; - btScalar k = btRecipSqrt (a); - p.setValue(0,-n[2]*k,n[1]*k); - // set q = n x p - q.setValue(a*k,-n[0]*p[2],n[0]*p[1]); - } - else { - // choose p in x-y plane - btScalar a = n.x()*n.x() + n.y()*n.y(); - btScalar k = btRecipSqrt (a); - p.setValue(-n.y()*k,n.x()*k,0); - // set q = n x p - q.setValue(-n.z()*p.y(),n.z()*p.x(),a*k); - } -} + @@ -117,10 +96,8 @@ public: static void calculateDiffAxisAngleQuaternion(const btQuaternion& orn0,const btQuaternion& orn1a,btVector3& axis,btScalar& angle) { - btQuaternion orn1 = orn0.farthest(orn1a); + btQuaternion orn1 = orn0.nearest(orn1a); btQuaternion dorn = orn1 * orn0.inverse(); - ///floating point inaccuracy can lead to w component > 1..., which breaks - dorn.normalize(); angle = dorn.getAngle(); axis = btVector3(dorn.x(),dorn.y(),dorn.z()); axis[3] = btScalar(0.); @@ -209,7 +186,7 @@ public: btTransformUtil::calculateVelocityQuaternion(m_posB,toPosB,m_ornB,toOrnB,btScalar(1.),linVelB,angVelB); btScalar maxAngularProjectedVelocity = angVelA.length() * m_boundingRadiusA + angVelB.length() * m_boundingRadiusB; btVector3 relLinVel = (linVelB-linVelA); - btScalar relLinVelocLength = (linVelB-linVelA).dot(m_separatingNormal); + btScalar relLinVelocLength = relLinVel.dot(m_separatingNormal); if (relLinVelocLength<0.f) { relLinVelocLength = 0.f; @@ -227,17 +204,21 @@ public: void initSeparatingDistance(const btVector3& separatingVector,btScalar separatingDistance,const btTransform& transA,const btTransform& transB) { - m_separatingNormal = separatingVector; m_separatingDistance = separatingDistance; - - const btVector3& toPosA = transA.getOrigin(); - const btVector3& toPosB = transB.getOrigin(); - btQuaternion toOrnA = transA.getRotation(); - btQuaternion toOrnB = transB.getRotation(); - m_posA = toPosA; - m_posB = toPosB; - m_ornA = toOrnA; - m_ornB = toOrnB; + + if (m_separatingDistance>0.f) + { + m_separatingNormal = separatingVector; + + const btVector3& toPosA = transA.getOrigin(); + const btVector3& toPosB = transB.getOrigin(); + btQuaternion toOrnA = transA.getRotation(); + btQuaternion toOrnB = transB.getRotation(); + m_posA = toPosA; + m_posB = toPosB; + m_ornA = toOrnA; + m_ornB = toOrnB; + } } }; diff --git a/extern/bullet2/src/LinearMath/btVector3.h b/extern/bullet2/src/LinearMath/btVector3.h index 5d5c39e8587..068e87c94ab 100644 --- a/extern/bullet2/src/LinearMath/btVector3.h +++ b/extern/bullet2/src/LinearMath/btVector3.h @@ -19,30 +19,37 @@ subject to the following restrictions: #include "btScalar.h" -#include "btScalar.h" #include "btMinMax.h" + +#ifdef BT_USE_DOUBLE_PRECISION +#define btVector3Data btVector3DoubleData +#define btVector3DataName "btVector3DoubleData" +#else +#define btVector3Data btVector3FloatData +#define btVector3DataName "btVector3FloatData" +#endif //BT_USE_DOUBLE_PRECISION + + + + /**@brief btVector3 can be used to represent 3D points and vectors. * It has an un-used w component to suit 16-byte alignment when btVector3 is stored in containers. This extra component can be used by derived classes (Quaternion?) or by user * Ideally, this class should be replaced by a platform optimized SIMD version that keeps the data in registers */ - ATTRIBUTE_ALIGNED16(class) btVector3 { public: #if defined (__SPU__) && defined (__CELLOS_LV2__) - union { - vec_float4 mVec128; btScalar m_floats[4]; - }; public: - vec_float4 get128() const + SIMD_FORCE_INLINE const vec_float4& get128() const { - return mVec128; + return *((const vec_float4*)&m_floats[0]); } public: #else //__CELLOS_LV2__ __SPU__ -#ifdef BT_USE_SSE // WIN32 +#ifdef BT_USE_SSE // _WIN32 union { __m128 mVec128; btScalar m_floats[4]; @@ -141,6 +148,19 @@ public: * This is symantically treating the vector like a point */ SIMD_FORCE_INLINE btScalar distance(const btVector3& v) const; + SIMD_FORCE_INLINE btVector3& safeNormalize() + { + btVector3 absVec = this->absolute(); + int maxIndex = absVec.maxAxis(); + if (absVec[maxIndex]>0) + { + *this /= absVec[maxIndex]; + return *this /= length(); + } + setValue(1,0,0); + return *this; + } + /**@brief Normalize this vector * x^2 + y^2 + z^2 = 1 */ SIMD_FORCE_INLINE btVector3& normalize() @@ -151,10 +171,10 @@ public: /**@brief Return a normalized version of this vector */ SIMD_FORCE_INLINE btVector3 normalized() const; - /**@brief Rotate this vector + /**@brief Return a rotated version of this vector * @param wAxis The axis to rotate about * @param angle The angle to rotate by */ - SIMD_FORCE_INLINE btVector3 rotate( const btVector3& wAxis, const btScalar angle ); + SIMD_FORCE_INLINE btVector3 rotate( const btVector3& wAxis, const btScalar angle ) const; /**@brief Return the angle between this and another vector * @param v The other vector */ @@ -306,7 +326,7 @@ public: m_floats[0]=x; m_floats[1]=y; m_floats[2]=z; - m_floats[3] = 0.f; + m_floats[3] = btScalar(0.); } void getSkewSymmetricMatrix(btVector3* v0,btVector3* v1,btVector3* v2) const @@ -316,6 +336,33 @@ public: v2->setValue(-y() ,x() ,0.); } + void setZero() + { + setValue(btScalar(0.),btScalar(0.),btScalar(0.)); + } + + SIMD_FORCE_INLINE bool isZero() const + { + return m_floats[0] == btScalar(0) && m_floats[1] == btScalar(0) && m_floats[2] == btScalar(0); + } + + SIMD_FORCE_INLINE bool fuzzyZero() const + { + return length2() < SIMD_EPSILON; + } + + SIMD_FORCE_INLINE void serialize(struct btVector3Data& dataOut) const; + + SIMD_FORCE_INLINE void deSerialize(const struct btVector3Data& dataIn); + + SIMD_FORCE_INLINE void serializeFloat(struct btVector3FloatData& dataOut) const; + + SIMD_FORCE_INLINE void deSerializeFloat(const struct btVector3FloatData& dataIn); + + SIMD_FORCE_INLINE void serializeDouble(struct btVector3DoubleData& dataOut) const; + + SIMD_FORCE_INLINE void deSerializeDouble(const struct btVector3DoubleData& dataIn); + }; /**@brief Return the sum of two vectors (Point symantics)*/ @@ -376,7 +423,7 @@ operator/(const btVector3& v1, const btVector3& v2) /**@brief Return the dot product between two vectors */ SIMD_FORCE_INLINE btScalar -dot(const btVector3& v1, const btVector3& v2) +btDot(const btVector3& v1, const btVector3& v2) { return v1.dot(v2); } @@ -384,7 +431,7 @@ dot(const btVector3& v1, const btVector3& v2) /**@brief Return the distance squared between two vectors */ SIMD_FORCE_INLINE btScalar -distance2(const btVector3& v1, const btVector3& v2) +btDistance2(const btVector3& v1, const btVector3& v2) { return v1.distance2(v2); } @@ -392,27 +439,27 @@ distance2(const btVector3& v1, const btVector3& v2) /**@brief Return the distance between two vectors */ SIMD_FORCE_INLINE btScalar -distance(const btVector3& v1, const btVector3& v2) +btDistance(const btVector3& v1, const btVector3& v2) { return v1.distance(v2); } /**@brief Return the angle between two vectors */ SIMD_FORCE_INLINE btScalar -angle(const btVector3& v1, const btVector3& v2) +btAngle(const btVector3& v1, const btVector3& v2) { return v1.angle(v2); } /**@brief Return the cross product of two vectors */ SIMD_FORCE_INLINE btVector3 -cross(const btVector3& v1, const btVector3& v2) +btCross(const btVector3& v1, const btVector3& v2) { return v1.cross(v2); } SIMD_FORCE_INLINE btScalar -triple(const btVector3& v1, const btVector3& v2, const btVector3& v3) +btTriple(const btVector3& v1, const btVector3& v2, const btVector3& v3) { return v1.triple(v2, v3); } @@ -444,7 +491,7 @@ SIMD_FORCE_INLINE btVector3 btVector3::normalized() const return *this / length(); } -SIMD_FORCE_INLINE btVector3 btVector3::rotate( const btVector3& wAxis, const btScalar angle ) +SIMD_FORCE_INLINE btVector3 btVector3::rotate( const btVector3& wAxis, const btScalar angle ) const { // wAxis must be a unit lenght vector @@ -488,7 +535,7 @@ public: SIMD_FORCE_INLINE int maxAxis4() const { int maxIndex = -1; - btScalar maxVal = btScalar(-1e30); + btScalar maxVal = btScalar(-BT_LARGE_FLOAT); if (m_floats[0] > maxVal) { maxIndex = 0; @@ -521,7 +568,7 @@ public: SIMD_FORCE_INLINE int minAxis4() const { int minIndex = -1; - btScalar minVal = btScalar(1e30); + btScalar minVal = btScalar(BT_LARGE_FLOAT); if (m_floats[0] < minVal) { minIndex = 0; @@ -585,8 +632,6 @@ public: } - - }; @@ -635,4 +680,87 @@ SIMD_FORCE_INLINE void btUnSwapVector3Endian(btVector3& vector) vector = swappedVec; } +template <class T> +SIMD_FORCE_INLINE void btPlaneSpace1 (const T& n, T& p, T& q) +{ + if (btFabs(n[2]) > SIMDSQRT12) { + // choose p in y-z plane + btScalar a = n[1]*n[1] + n[2]*n[2]; + btScalar k = btRecipSqrt (a); + p[0] = 0; + p[1] = -n[2]*k; + p[2] = n[1]*k; + // set q = n x p + q[0] = a*k; + q[1] = -n[0]*p[2]; + q[2] = n[0]*p[1]; + } + else { + // choose p in x-y plane + btScalar a = n[0]*n[0] + n[1]*n[1]; + btScalar k = btRecipSqrt (a); + p[0] = -n[1]*k; + p[1] = n[0]*k; + p[2] = 0; + // set q = n x p + q[0] = -n[2]*p[1]; + q[1] = n[2]*p[0]; + q[2] = a*k; + } +} + + +struct btVector3FloatData +{ + float m_floats[4]; +}; + +struct btVector3DoubleData +{ + double m_floats[4]; + +}; + +SIMD_FORCE_INLINE void btVector3::serializeFloat(struct btVector3FloatData& dataOut) const +{ + ///could also do a memcpy, check if it is worth it + for (int i=0;i<4;i++) + dataOut.m_floats[i] = float(m_floats[i]); +} + +SIMD_FORCE_INLINE void btVector3::deSerializeFloat(const struct btVector3FloatData& dataIn) +{ + for (int i=0;i<4;i++) + m_floats[i] = btScalar(dataIn.m_floats[i]); +} + + +SIMD_FORCE_INLINE void btVector3::serializeDouble(struct btVector3DoubleData& dataOut) const +{ + ///could also do a memcpy, check if it is worth it + for (int i=0;i<4;i++) + dataOut.m_floats[i] = double(m_floats[i]); +} + +SIMD_FORCE_INLINE void btVector3::deSerializeDouble(const struct btVector3DoubleData& dataIn) +{ + for (int i=0;i<4;i++) + m_floats[i] = btScalar(dataIn.m_floats[i]); +} + + +SIMD_FORCE_INLINE void btVector3::serialize(struct btVector3Data& dataOut) const +{ + ///could also do a memcpy, check if it is worth it + for (int i=0;i<4;i++) + dataOut.m_floats[i] = m_floats[i]; +} + +SIMD_FORCE_INLINE void btVector3::deSerialize(const struct btVector3Data& dataIn) +{ + for (int i=0;i<4;i++) + m_floats[i] = dataIn.m_floats[i]; +} + + #endif //SIMD__VECTOR3_H |