update bullet test to compile from source

1 files changed, 2749 insertions, 0 deletions

diff --git a/tests/bullet/src/LinearMath/btConvexHullComputer.cpp b/tests/bullet/src/LinearMath/btConvexHullComputer.cpp
new file mode 100644
index 00000000..10316b40
--- /dev/null
+++ b/tests/bullet/src/LinearMath/btConvexHullComputer.cpp
@@ -0,0 +1,2749 @@
+/*

+Copyright (c) 2011 Ole Kniemeyer, MAXON, www.maxon.net

+

+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.

+*/

+

+#include <string.h>

+

+#include "btConvexHullComputer.h"

+#include "btAlignedObjectArray.h"

+#include "btMinMax.h"

+#include "btVector3.h"

+

+#ifdef __GNUC__

+	#include <stdint.h>

+#elif defined(_MSC_VER)

+	typedef __int32 int32_t;

+	typedef __int64 int64_t;

+	typedef unsigned __int32 uint32_t;

+	typedef unsigned __int64 uint64_t;

+#else

+	typedef int int32_t;

+	typedef long long int int64_t;

+	typedef unsigned int uint32_t;

+	typedef unsigned long long int uint64_t;

+#endif

+

+

+//The definition of USE_X86_64_ASM is moved into the build system. You can enable it manually by commenting out the following lines

+//#if (defined(__GNUC__) && defined(__x86_64__) && !defined(__ICL))  // || (defined(__ICL) && defined(_M_X64))   bug in Intel compiler, disable inline assembly

+//	#define USE_X86_64_ASM

+//#endif

+

+

+//#define DEBUG_CONVEX_HULL

+//#define SHOW_ITERATIONS

+

+#if defined(DEBUG_CONVEX_HULL) || defined(SHOW_ITERATIONS)

+	#include <stdio.h>

+#endif

+

+// Convex hull implementation based on Preparata and Hong

+// Ole Kniemeyer, MAXON Computer GmbH

+class btConvexHullInternal

+{

+	public:

+		

+		class Point64

+		{

+			public:

+				int64_t x;

+				int64_t y;

+				int64_t z;

+				

+				Point64(int64_t x, int64_t y, int64_t z): x(x), y(y), z(z)

+				{

+				}

+

+				bool isZero()

+				{

+					return (x == 0) && (y == 0) && (z == 0);

+				}

+

+				int64_t dot(const Point64& b) const

+				{

+					return x * b.x + y * b.y + z * b.z;

+				}

+		};

+		

+		class Point32

+		{

+			public:

+				int32_t x;

+				int32_t y;

+				int32_t z;

+				int index;

+				

+				Point32()

+				{

+				}

+				

+				Point32(int32_t x, int32_t y, int32_t z): x(x), y(y), z(z), index(-1)

+				{

+				}

+				

+				bool operator==(const Point32& b) const

+				{

+					return (x == b.x) && (y == b.y) && (z == b.z);

+				}

+

+				bool operator!=(const Point32& b) const

+				{

+					return (x != b.x) || (y != b.y) || (z != b.z);

+				}

+

+				bool isZero()

+				{

+					return (x == 0) && (y == 0) && (z == 0);

+				}

+

+				Point64 cross(const Point32& b) const

+				{

+					return Point64(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x);

+				}

+

+				Point64 cross(const Point64& b) const

+				{

+					return Point64(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x);

+				}

+

+				int64_t dot(const Point32& b) const

+				{

+					return x * b.x + y * b.y + z * b.z;

+				}

+

+				int64_t dot(const Point64& b) const

+				{

+					return x * b.x + y * b.y + z * b.z;

+				}

+

+				Point32 operator+(const Point32& b) const

+				{

+					return Point32(x + b.x, y + b.y, z + b.z);

+				}

+

+				Point32 operator-(const Point32& b) const

+				{

+					return Point32(x - b.x, y - b.y, z - b.z);

+				}

+		};

+

+		class Int128

+		{

+			public:

+				uint64_t low;

+				uint64_t high;

+

+				Int128()

+				{

+				}

+

+				Int128(uint64_t low, uint64_t high): low(low), high(high)

+				{

+				}

+

+				Int128(uint64_t low): low(low), high(0)

+				{

+				}

+

+				Int128(int64_t value): low(value), high((value >= 0) ? 0 : (uint64_t) -1LL)

+				{

+				}

+

+				static Int128 mul(int64_t a, int64_t b);

+

+				static Int128 mul(uint64_t a, uint64_t b);

+

+				Int128 operator-() const

+				{

+					return Int128((uint64_t) -(int64_t)low, ~high + (low == 0));

+				}

+

+				Int128 operator+(const Int128& b) const

+				{

+#ifdef USE_X86_64_ASM

+					Int128 result;

+					__asm__ ("addq %[bl], %[rl]\n\t"

+									 "adcq %[bh], %[rh]\n\t"

+									 : [rl] "=r" (result.low), [rh] "=r" (result.high)

+									 : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high)

+									 : "cc" );

+					return result;

+#else

+					uint64_t lo = low + b.low;

+					return Int128(lo, high + b.high + (lo < low));

+#endif

+				}

+

+				Int128 operator-(const Int128& b) const

+				{

+#ifdef USE_X86_64_ASM

+					Int128 result;

+					__asm__ ("subq %[bl], %[rl]\n\t"

+									 "sbbq %[bh], %[rh]\n\t"

+									 : [rl] "=r" (result.low), [rh] "=r" (result.high)

+									 : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high)

+									 : "cc" );

+					return result;

+#else

+					return *this + -b;

+#endif

+				}

+

+				Int128& operator+=(const Int128& b)

+				{

+#ifdef USE_X86_64_ASM

+					__asm__ ("addq %[bl], %[rl]\n\t"

+									 "adcq %[bh], %[rh]\n\t"

+									 : [rl] "=r" (low), [rh] "=r" (high)

+									 : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high)

+									 : "cc" );

+#else

+					uint64_t lo = low + b.low;

+					if (lo < low)

+					{

+						++high;

+					}

+					low = lo;

+					high += b.high;

+#endif

+					return *this;

+				}

+

+				Int128& operator++()

+				{

+					if (++low == 0)

+					{

+						++high;

+					}

+					return *this;

+				}

+

+				Int128 operator*(int64_t b) const;

+

+				btScalar toScalar() const

+				{

+					return ((int64_t) high >= 0) ? btScalar(high) * (btScalar(0x100000000LL) * btScalar(0x100000000LL)) + btScalar(low)

+						: -(-*this).toScalar();

+				}

+

+				int getSign() const

+				{

+					return ((int64_t) high < 0) ? -1 : (high || low) ? 1 : 0;

+				}

+

+				bool operator<(const Int128& b) const

+				{

+					return (high < b.high) || ((high == b.high) && (low < b.low));

+				}

+

+				int ucmp(const Int128&b) const

+				{

+					if (high < b.high)

+					{

+						return -1;

+					}

+					if (high > b.high)

+					{

+						return 1;

+					}

+					if (low < b.low)

+					{

+						return -1;

+					}

+					if (low > b.low)

+					{

+						return 1;

+					}

+					return 0;

+				}

+		};

+

+

+		class Rational64

+		{

+			private:

+				uint64_t numerator;

+				uint64_t denominator;

+				int sign;

+				

+			public:

+				Rational64(int64_t numerator, int64_t denominator)

+				{

+					if (numerator > 0)

+					{

+						sign = 1;

+						this->numerator = (uint64_t) numerator;

+					}

+					else if (numerator < 0)

+					{

+						sign = -1;

+						this->numerator = (uint64_t) -numerator;

+					}

+					else

+					{

+						sign = 0;

+						this->numerator = 0;

+					}

+					if (denominator > 0)

+					{

+						this->denominator = (uint64_t) denominator;

+					}

+					else if (denominator < 0)

+					{

+						sign = -sign;

+						this->denominator = (uint64_t) -denominator;

+					}

+					else

+					{

+						this->denominator = 0;

+					}

+				}

+				

+				bool isNegativeInfinity() const

+				{

+					return (sign < 0) && (denominator == 0);

+				}

+				

+				bool isNaN() const

+				{

+					return (sign == 0) && (denominator == 0);

+				}

+				

+				int compare(const Rational64& b) const;

+				

+				btScalar toScalar() const

+				{

+					return sign * ((denominator == 0) ? SIMD_INFINITY : (btScalar) numerator / denominator);

+				}

+		};

+

+

+		class Rational128

+		{

+			private:

+				Int128 numerator;

+				Int128 denominator;

+				int sign;

+				bool isInt64;

+

+			public:

+				Rational128(int64_t value)

+				{

+					if (value > 0)

+					{

+						sign = 1;

+						this->numerator = value;

+					}

+					else if (value < 0)

+					{

+						sign = -1;

+						this->numerator = -value;

+					}

+					else

+					{

+						sign = 0;

+						this->numerator = (uint64_t) 0;

+					}

+					this->denominator = (uint64_t) 1;

+					isInt64 = true;

+				}

+

+				Rational128(const Int128& numerator, const Int128& denominator)

+				{

+					sign = numerator.getSign();

+					if (sign >= 0)

+					{

+						this->numerator = numerator;

+					}

+					else

+					{

+						this->numerator = -numerator;

+					}

+					int dsign = denominator.getSign();

+					if (dsign >= 0)

+					{

+						this->denominator = denominator;

+					}

+					else

+					{

+						sign = -sign;

+						this->denominator = -denominator;

+					}

+					isInt64 = false;

+				}

+

+				int compare(const Rational128& b) const;

+

+				int compare(int64_t b) const;

+

+				btScalar toScalar() const

+				{

+					return sign * ((denominator.getSign() == 0) ? SIMD_INFINITY : numerator.toScalar() / denominator.toScalar());

+				}

+		};

+

+		class PointR128

+		{

+			public:

+				Int128 x;

+				Int128 y;

+				Int128 z;

+				Int128 denominator;

+

+				PointR128()

+				{

+				}

+

+				PointR128(Int128 x, Int128 y, Int128 z, Int128 denominator): x(x), y(y), z(z), denominator(denominator)

+				{

+				}

+

+				btScalar xvalue() const

+				{

+					return x.toScalar() / denominator.toScalar();

+				}

+

+				btScalar yvalue() const

+				{

+					return y.toScalar() / denominator.toScalar();

+				}

+

+				btScalar zvalue() const

+				{

+					return z.toScalar() / denominator.toScalar();

+				}

+		};

+

+

+		class Edge;

+		class Face;

+

+		class Vertex

+		{

+			public:

+				Vertex* next;

+				Vertex* prev;

+				Edge* edges;

+				Face* firstNearbyFace;

+				Face* lastNearbyFace;

+				PointR128 point128;

+				Point32 point;

+				int copy;

+				

+				Vertex(): next(NULL), prev(NULL), edges(NULL), firstNearbyFace(NULL), lastNearbyFace(NULL), copy(-1)

+				{

+				}

+

+#ifdef DEBUG_CONVEX_HULL

+				void print()

+				{

+					printf("V%d (%d, %d, %d)", point.index, point.x, point.y, point.z);

+				}

+

+				void printGraph();

+#endif

+

+				Point32 operator-(const Vertex& b) const

+				{

+					return point - b.point;

+				}

+

+				Rational128 dot(const Point64& b) const

+				{

+					return (point.index >= 0) ? Rational128(point.dot(b))

+						: Rational128(point128.x * b.x + point128.y * b.y + point128.z * b.z, point128.denominator);

+				}

+

+				btScalar xvalue() const

+				{

+					return (point.index >= 0) ? btScalar(point.x) : point128.xvalue();

+				}

+

+				btScalar yvalue() const

+				{

+					return (point.index >= 0) ? btScalar(point.y) : point128.yvalue();

+				}

+

+				btScalar zvalue() const

+				{

+					return (point.index >= 0) ? btScalar(point.z) : point128.zvalue();

+				}

+

+				void receiveNearbyFaces(Vertex* src)

+				{

+					if (lastNearbyFace)

+					{

+						lastNearbyFace->nextWithSameNearbyVertex = src->firstNearbyFace;

+					}

+					else

+					{

+						firstNearbyFace = src->firstNearbyFace;

+					}

+					if (src->lastNearbyFace)

+					{

+						lastNearbyFace = src->lastNearbyFace;

+					}

+					for (Face* f = src->firstNearbyFace; f; f = f->nextWithSameNearbyVertex)

+					{

+						btAssert(f->nearbyVertex == src);

+						f->nearbyVertex = this;

+					}

+					src->firstNearbyFace = NULL;

+					src->lastNearbyFace = NULL;

+				}

+		};

+

+

+		class Edge

+		{

+			public:

+				Edge* next;

+				Edge* prev;

+				Edge* reverse;

+				Vertex* target;

+				Face* face;

+				int copy;

+

+				~Edge()

+				{

+					next = NULL;

+					prev = NULL;

+					reverse = NULL;

+					target = NULL;

+					face = NULL;

+				}

+

+				void link(Edge* n)

+				{

+					btAssert(reverse->target == n->reverse->target);

+					next = n;

+					n->prev = this;

+				}

+

+#ifdef DEBUG_CONVEX_HULL

+				void print()

+				{

+					printf("E%p : %d -> %d,  n=%p p=%p   (0 %d\t%d\t%d) -> (%d %d %d)", this, reverse->target->point.index, target->point.index, next, prev,

+								 reverse->target->point.x, reverse->target->point.y, reverse->target->point.z, target->point.x, target->point.y, target->point.z);

+				}

+#endif

+		};

+

+		class Face

+		{

+			public:

+				Face* next;

+				Vertex* nearbyVertex;

+				Face* nextWithSameNearbyVertex;

+				Point32 origin;

+				Point32 dir0;

+				Point32 dir1;

+

+				Face(): next(NULL), nearbyVertex(NULL), nextWithSameNearbyVertex(NULL)

+				{

+				}

+

+				void init(Vertex* a, Vertex* b, Vertex* c)

+				{

+					nearbyVertex = a;

+					origin = a->point;

+					dir0 = *b - *a;

+					dir1 = *c - *a;

+					if (a->lastNearbyFace)

+					{

+						a->lastNearbyFace->nextWithSameNearbyVertex = this;

+					}

+					else

+					{

+						a->firstNearbyFace = this;

+					}

+					a->lastNearbyFace = this;

+				}

+

+				Point64 getNormal()

+				{

+					return dir0.cross(dir1);

+				}

+		};

+

+		template<typename UWord, typename UHWord> class DMul

+		{

+			private:

+				static uint32_t high(uint64_t value)

+				{

+					return (uint32_t) (value >> 32);

+				}

+				

+				static uint32_t low(uint64_t value)

+				{

+					return (uint32_t) value;

+				}

+				

+				static uint64_t mul(uint32_t a, uint32_t b)

+				{

+					return (uint64_t) a * (uint64_t) b;

+				}

+				

+				static void shlHalf(uint64_t& value)

+				{

+					value <<= 32;

+				}

+				

+				static uint64_t high(Int128 value)

+				{

+					return value.high;

+				}

+				

+				static uint64_t low(Int128 value)

+				{

+					return value.low;

+				}

+				

+				static Int128 mul(uint64_t a, uint64_t b)

+				{

+					return Int128::mul(a, b);

+				}

+				

+				static void shlHalf(Int128& value)

+				{

+					value.high = value.low;

+					value.low = 0;

+				}

+				

+			public:

+				

+				static void mul(UWord a, UWord b, UWord& resLow, UWord& resHigh)

+				{

+					UWord p00 = mul(low(a), low(b));

+					UWord p01 = mul(low(a), high(b));

+					UWord p10 = mul(high(a), low(b));

+					UWord p11 = mul(high(a), high(b));

+					UWord p0110 = UWord(low(p01)) + UWord(low(p10));

+					p11 += high(p01);

+					p11 += high(p10);

+					p11 += high(p0110);

+					shlHalf(p0110);

+					p00 += p0110;

+					if (p00 < p0110)

+					{

+						++p11;

+					}

+					resLow = p00;

+					resHigh = p11;

+				}

+		};

+	

+	private:

+

+		class IntermediateHull

+		{

+			public:

+				Vertex* minXy;

+				Vertex* maxXy;

+				Vertex* minYx;

+				Vertex* maxYx;

+				

+				IntermediateHull(): minXy(NULL), maxXy(NULL), minYx(NULL), maxYx(NULL)

+				{

+				}

+				

+				void print();

+		};

+	

+		enum Orientation {NONE, CLOCKWISE, COUNTER_CLOCKWISE};

+

+		template <typename T> class PoolArray

+		{

+			private:

+				T* array;

+				int size;

+

+			public:

+				PoolArray<T>* next;

+

+				PoolArray(int size): size(size), next(NULL)

+				{

+					array = (T*) btAlignedAlloc(sizeof(T) * size, 16);

+				}

+

+				~PoolArray()

+				{

+					btAlignedFree(array);

+				}

+

+				T* init()

+				{

+					T* o = array;

+					for (int i = 0; i < size; i++, o++)

+					{

+						o->next = (i+1 < size) ? o + 1 : NULL;

+					}

+					return array;

+				}

+		};

+

+		template <typename T> class Pool

+		{

+			private:

+				PoolArray<T>* arrays;

+				PoolArray<T>* nextArray;

+				T* freeObjects;

+				int arraySize;

+

+			public:

+				Pool(): arrays(NULL), nextArray(NULL), freeObjects(NULL), arraySize(256)

+				{

+				}

+

+				~Pool()

+				{

+					while (arrays)

+					{

+						PoolArray<T>* p = arrays;

+						arrays = p->next;

+						p->~PoolArray<T>();

+						btAlignedFree(p);

+					}

+				}

+

+				void reset()

+				{

+					nextArray = arrays;

+					freeObjects = NULL;

+				}

+

+				void setArraySize(int arraySize)

+				{

+					this->arraySize = arraySize;

+				}

+

+				T* newObject()

+				{

+					T* o = freeObjects;

+					if (!o)

+					{

+						PoolArray<T>* p = nextArray;

+						if (p)

+						{

+							nextArray = p->next;

+						}

+						else

+						{

+							p = new(btAlignedAlloc(sizeof(PoolArray<T>), 16)) PoolArray<T>(arraySize);

+							p->next = arrays;

+							arrays = p;

+						}

+						o = p->init();

+					}

+					freeObjects = o->next;

+					return new(o) T();

+				};

+

+				void freeObject(T* object)

+				{

+					object->~T();

+					object->next = freeObjects;

+					freeObjects = object;

+				}

+		};

+

+		btVector3 scaling;

+		btVector3 center;

+		Pool<Vertex> vertexPool;

+		Pool<Edge> edgePool;

+		Pool<Face> facePool;

+		btAlignedObjectArray<Vertex*> originalVertices;

+		int mergeStamp;

+		int minAxis;

+		int medAxis;

+		int maxAxis;

+		int usedEdgePairs;

+		int maxUsedEdgePairs;

+

+		static Orientation getOrientation(const Edge* prev, const Edge* next, const Point32& s, const Point32& t);

+		Edge* findMaxAngle(bool ccw, const Vertex* start, const Point32& s, const Point64& rxs, const Point64& sxrxs, Rational64& minCot);

+		void findEdgeForCoplanarFaces(Vertex* c0, Vertex* c1, Edge*& e0, Edge*& e1, Vertex* stop0, Vertex* stop1);

+

+		Edge* newEdgePair(Vertex* from, Vertex* to);

+

+		void removeEdgePair(Edge* edge)

+		{

+			Edge* n = edge->next;

+			Edge* r = edge->reverse;

+

+			btAssert(edge->target && r->target);

+

+			if (n != edge)

+			{

+				n->prev = edge->prev;

+				edge->prev->next = n;

+				r->target->edges = n;

+			}

+			else

+			{

+				r->target->edges = NULL;

+			}

+			

+			n = r->next;

+			

+			if (n != r)

+			{

+				n->prev = r->prev;

+				r->prev->next = n;

+				edge->target->edges = n;

+			}

+			else

+			{

+				edge->target->edges = NULL;

+			}

+

+			edgePool.freeObject(edge);

+			edgePool.freeObject(r);

+			usedEdgePairs--;

+		}

+		

+		void computeInternal(int start, int end, IntermediateHull& result);

+		

+		bool mergeProjection(IntermediateHull& h0, IntermediateHull& h1, Vertex*& c0, Vertex*& c1);

+		

+		void merge(IntermediateHull& h0, IntermediateHull& h1);

+

+		btVector3 toBtVector(const Point32& v);

+

+		btVector3 getBtNormal(Face* face);

+

+		bool shiftFace(Face* face, btScalar amount, btAlignedObjectArray<Vertex*> stack);

+

+	public:

+		Vertex* vertexList;

+

+		void compute(const void* coords, bool doubleCoords, int stride, int count);

+

+		btVector3 getCoordinates(const Vertex* v);

+

+		btScalar shrink(btScalar amount, btScalar clampAmount);

+};

+

+

+btConvexHullInternal::Int128 btConvexHullInternal::Int128::operator*(int64_t b) const

+{

+	bool negative = (int64_t) high < 0;

+	Int128 a = negative ? -*this : *this;

+	if (b < 0)

+	{

+		negative = !negative;

+		b = -b;

+	}

+	Int128 result = mul(a.low, (uint64_t) b);

+	result.high += a.high * (uint64_t) b;

+	return negative ? -result : result;

+}

+

+btConvexHullInternal::Int128 btConvexHullInternal::Int128::mul(int64_t a, int64_t b)

+{

+	Int128 result;

+	

+#ifdef USE_X86_64_ASM

+	__asm__ ("imulq %[b]"

+					 : "=a" (result.low), "=d" (result.high)

+					 : "0"(a), [b] "r"(b)

+					 : "cc" );

+	return result;

+	

+#else

+	bool negative = a < 0;

+	if (negative)

+	{

+		a = -a;

+	}

+	if (b < 0)

+	{

+		negative = !negative;

+		b = -b;

+	}

+	DMul<uint64_t, uint32_t>::mul((uint64_t) a, (uint64_t) b, result.low, result.high);

+	return negative ? -result : result;

+#endif

+}

+

+btConvexHullInternal::Int128 btConvexHullInternal::Int128::mul(uint64_t a, uint64_t b)

+{

+	Int128 result;

+

+#ifdef USE_X86_64_ASM

+	__asm__ ("mulq %[b]"

+					 : "=a" (result.low), "=d" (result.high)

+					 : "0"(a), [b] "r"(b)

+					 : "cc" );

+

+#else

+	DMul<uint64_t, uint32_t>::mul(a, b, result.low, result.high);

+#endif

+

+	return result;

+}

+

+int btConvexHullInternal::Rational64::compare(const Rational64& b) const

+{

+	if (sign != b.sign)

+	{

+		return sign - b.sign;

+	}

+	else if (sign == 0)

+	{

+		return 0;

+	}

+

+	//	return (numerator * b.denominator > b.numerator * denominator) ? sign : (numerator * b.denominator < b.numerator * denominator) ? -sign : 0;

+

+#ifdef USE_X86_64_ASM

+

+	int result;

+	int64_t tmp;

+	int64_t dummy;

+	__asm__ ("mulq %[bn]\n\t"

+					 "movq %%rax, %[tmp]\n\t"

+					 "movq %%rdx, %%rbx\n\t"

+					 "movq %[tn], %%rax\n\t"

+					 "mulq %[bd]\n\t"

+					 "subq %[tmp], %%rax\n\t"

+					 "sbbq %%rbx, %%rdx\n\t" // rdx:rax contains 128-bit-difference "numerator*b.denominator - b.numerator*denominator"

+					 "setnsb %%bh\n\t" // bh=1 if difference is non-negative, bh=0 otherwise

+					 "orq %%rdx, %%rax\n\t"

+					 "setnzb %%bl\n\t" // bl=1 if difference if non-zero, bl=0 if it is zero

+					 "decb %%bh\n\t" // now bx=0x0000 if difference is zero, 0xff01 if it is negative, 0x0001 if it is positive (i.e., same sign as difference)

+					 "shll $16, %%ebx\n\t" // ebx has same sign as difference

+					 : "=&b"(result), [tmp] "=&r"(tmp), "=a"(dummy)

+					 : "a"(denominator), [bn] "g"(b.numerator), [tn] "g"(numerator), [bd] "g"(b.denominator)

+					 : "%rdx", "cc" );

+	return result ? result ^ sign // if sign is +1, only bit 0 of result is inverted, which does not change the sign of result (and cannot result in zero)

+																// if sign is -1, all bits of result are inverted, which changes the sign of result (and again cannot result in zero)

+								: 0;

+

+#else

+

+	return sign * Int128::mul(numerator, b.denominator).ucmp(Int128::mul(denominator, b.numerator));

+

+#endif

+}

+

+int btConvexHullInternal::Rational128::compare(const Rational128& b) const

+{

+	if (sign != b.sign)

+	{

+		return sign - b.sign;

+	}

+	else if (sign == 0)

+	{

+		return 0;

+	}

+	if (isInt64)

+	{

+		return -b.compare(sign * (int64_t) numerator.low);

+	}

+

+	Int128 nbdLow, nbdHigh, dbnLow, dbnHigh;

+	DMul<Int128, uint64_t>::mul(numerator, b.denominator, nbdLow, nbdHigh);

+	DMul<Int128, uint64_t>::mul(denominator, b.numerator, dbnLow, dbnHigh);

+

+	int cmp = nbdHigh.ucmp(dbnHigh);

+	if (cmp)

+	{

+		return cmp * sign;

+	}

+	return nbdLow.ucmp(dbnLow) * sign;

+}

+

+int btConvexHullInternal::Rational128::compare(int64_t b) const

+{

+	if (isInt64)

+	{

+		int64_t a = sign * (int64_t) numerator.low;

+		return (a > b) ? 1 : (a < b) ? -1 : 0;

+	}

+	if (b > 0)

+	{

+		if (sign <= 0)

+		{

+			return -1;

+		}

+	}

+	else if (b < 0)

+	{

+		if (sign >= 0)

+		{

+			return 1;

+		}

+		b = -b;

+	}

+	else

+	{

+		return sign;

+	}

+

+	return numerator.ucmp(denominator * b) * sign;

+}

+

+

+btConvexHullInternal::Edge* btConvexHullInternal::newEdgePair(Vertex* from, Vertex* to)

+{

+	btAssert(from && to);

+	Edge* e = edgePool.newObject();

+	Edge* r = edgePool.newObject();

+	e->reverse = r;

+	r->reverse = e;

+	e->copy = mergeStamp;

+	r->copy = mergeStamp;

+	e->target = to;

+	r->target = from;

+	e->face = NULL;

+	r->face = NULL;

+	usedEdgePairs++;

+	if (usedEdgePairs > maxUsedEdgePairs)

+	{

+		maxUsedEdgePairs = usedEdgePairs;

+	}

+	return e;

+}

+

+bool btConvexHullInternal::mergeProjection(IntermediateHull& h0, IntermediateHull& h1, Vertex*& c0, Vertex*& c1)

+{

+	Vertex* v0 = h0.maxYx;

+	Vertex* v1 = h1.minYx;

+	if ((v0->point.x == v1->point.x) && (v0->point.y == v1->point.y))

+	{

+		btAssert(v0->point.z < v1->point.z);

+		Vertex* v1p = v1->prev;

+		if (v1p == v1)

+		{

+			c0 = v0;

+			if (v1->edges)

+			{

+				btAssert(v1->edges->next == v1->edges);

+				v1 = v1->edges->target;

+				btAssert(v1->edges->next == v1->edges);

+			}

+			c1 = v1;

+			return false;

+		}

+		Vertex* v1n = v1->next;

+		v1p->next = v1n;

+		v1n->prev = v1p;

+		if (v1 == h1.minXy)

+		{

+			if ((v1n->point.x < v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y < v1p->point.y)))

+			{

+				h1.minXy = v1n;

+			}

+			else

+			{

+				h1.minXy = v1p;

+			}

+		}

+		if (v1 == h1.maxXy)

+		{

+			if ((v1n->point.x > v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y > v1p->point.y)))

+			{

+				h1.maxXy = v1n;

+			}

+			else

+			{

+				h1.maxXy = v1p;

+			}

+		}

+	}

+	

+	v0 = h0.maxXy;

+	v1 = h1.maxXy;

+	Vertex* v00 = NULL;

+	Vertex* v10 = NULL;

+	int32_t sign = 1;

+

+	for (int side = 0; side <= 1; side++)

+	{		

+		int32_t dx = (v1->point.x - v0->point.x) * sign;

+		if (dx > 0)

+		{

+			while (true)

+			{

+				int32_t dy = v1->point.y - v0->point.y;

+

+				Vertex* w0 = side ? v0->next : v0->prev;

+				if (w0 != v0)

+				{

+					int32_t dx0 = (w0->point.x - v0->point.x) * sign;

+					int32_t dy0 = w0->point.y - v0->point.y;

+					if ((dy0 <= 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx <= dy * dx0))))

+					{

+						v0 = w0;

+						dx = (v1->point.x - v0->point.x) * sign;

+						continue;

+					}

+				}

+

+				Vertex* w1 = side ? v1->next : v1->prev;

+				if (w1 != v1)

+				{

+					int32_t dx1 = (w1->point.x - v1->point.x) * sign;

+					int32_t dy1 = w1->point.y - v1->point.y;

+					int32_t dxn = (w1->point.x - v0->point.x) * sign;

+					if ((dxn > 0) && (dy1 < 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx < dy * dx1))))

+					{

+						v1 = w1;

+						dx = dxn;

+						continue;

+					}

+				}

+

+				break;

+			}

+		}

+		else if (dx < 0)

+		{

+			while (true)

+			{

+				int32_t dy = v1->point.y - v0->point.y;

+				

+				Vertex* w1 = side ? v1->prev : v1->next;

+				if (w1 != v1)

+				{

+					int32_t dx1 = (w1->point.x - v1->point.x) * sign;

+					int32_t dy1 = w1->point.y - v1->point.y;

+					if ((dy1 >= 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx <= dy * dx1))))

+					{

+						v1 = w1;

+						dx = (v1->point.x - v0->point.x) * sign;

+						continue;

+					}

+				}

+				

+				Vertex* w0 = side ? v0->prev : v0->next;

+				if (w0 != v0)

+				{

+					int32_t dx0 = (w0->point.x - v0->point.x) * sign;

+					int32_t dy0 = w0->point.y - v0->point.y;

+					int32_t dxn = (v1->point.x - w0->point.x) * sign;

+					if ((dxn < 0) && (dy0 > 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx < dy * dx0))))

+					{

+						v0 = w0;

+						dx = dxn;

+						continue;

+					}

+				}

+				

+				break;

+			}

+		}

+		else

+		{

+			int32_t x = v0->point.x;

+			int32_t y0 = v0->point.y;

+			Vertex* w0 = v0;

+			Vertex* t;

+			while (((t = side ? w0->next : w0->prev) != v0) && (t->point.x == x) && (t->point.y <= y0))

+			{

+				w0 = t;

+				y0 = t->point.y;

+			}

+			v0 = w0;

+

+			int32_t y1 = v1->point.y;

+			Vertex* w1 = v1;

+			while (((t = side ? w1->prev : w1->next) != v1) && (t->point.x == x) && (t->point.y >= y1))

+			{

+				w1 = t;

+				y1 = t->point.y;

+			}

+			v1 = w1;

+		}

+		

+		if (side == 0)

+		{

+			v00 = v0;

+			v10 = v1;

+

+			v0 = h0.minXy;

+			v1 = h1.minXy;

+			sign = -1;

+		}

+	}

+

+	v0->prev = v1;

+	v1->next = v0;

+

+	v00->next = v10;

+	v10->prev = v00;

+

+	if (h1.minXy->point.x < h0.minXy->point.x)

+	{

+		h0.minXy = h1.minXy;

+	}

+	if (h1.maxXy->point.x >= h0.maxXy->point.x)

+	{

+		h0.maxXy = h1.maxXy;

+	}

+	

+	h0.maxYx = h1.maxYx;

+

+	c0 = v00;

+	c1 = v10;

+

+	return true;

+}

+

+void btConvexHullInternal::computeInternal(int start, int end, IntermediateHull& result)

+{

+	int n = end - start;

+	switch (n)

+	{

+		case 0:

+			result.minXy = NULL;

+			result.maxXy = NULL;

+			result.minYx = NULL;

+			result.maxYx = NULL;

+			return;

+		case 2:

+		{

+			Vertex* v = originalVertices[start];

+			Vertex* w = v + 1;

+			if (v->point != w->point)

+			{

+				int32_t dx = v->point.x - w->point.x;

+				int32_t dy = v->point.y - w->point.y;

+

+				if ((dx == 0) && (dy == 0))

+				{

+					if (v->point.z > w->point.z)

+					{

+						Vertex* t = w;

+						w = v;

+						v = t;

+					}

+					btAssert(v->point.z < w->point.z);

+					v->next = v;

+					v->prev = v;

+					result.minXy = v;

+					result.maxXy = v;

+					result.minYx = v;

+					result.maxYx = v;

+				}

+				else

+				{

+					v->next = w;

+					v->prev = w;

+					w->next = v;

+					w->prev = v;

+

+					if ((dx < 0) || ((dx == 0) && (dy < 0)))

+					{

+						result.minXy = v;

+						result.maxXy = w;

+					}

+					else

+					{

+						result.minXy = w;

+						result.maxXy = v;

+