merge

7 files changed, 574 insertions, 402 deletions

diff --git a/indra/llmath/CMakeLists.txt b/indra/llmath/CMakeLists.txt
index 367486eee7..dda07133d5 100644
--- a/indra/llmath/CMakeLists.txt
+++ b/indra/llmath/CMakeLists.txt
@@ -22,6 +22,7 @@ set(llmath_SOURCE_FILES
     llsphere.cpp
     llvolume.cpp
     llvolumemgr.cpp
+    llvolumeoctree.cpp
     llsdutil_math.cpp
     m3math.cpp
     m4math.cpp
@@ -66,6 +67,7 @@ set(llmath_HEADER_FILES
     llmatrix4a.h
     llvolume.h
     llvolumemgr.h
+    llvolumeoctree.h
     llsdutil_math.h
     m3math.h
     m4math.h
diff --git a/indra/llmath/llcamera.cpp b/indra/llmath/llcamera.cpp
index 487ed6451f..6b56e4870e 100644
--- a/indra/llmath/llcamera.cpp
+++ b/indra/llmath/llcamera.cpp
@@ -48,10 +48,10 @@ LLCamera::LLCamera() :
 	mPlaneCount(6),
 	mFrustumCornerDist(0.f)
 {
+	alignPlanes();
 	calculateFrustumPlanes();
 } 
 
-
 LLCamera::LLCamera(F32 vertical_fov_rads, F32 aspect_ratio, S32 view_height_in_pixels, F32 near_plane, F32 far_plane) :
 	LLCoordFrame(),
 	mViewHeightInPixels(view_height_in_pixels),
@@ -59,6 +59,7 @@ LLCamera::LLCamera(F32 vertical_fov_rads, F32 aspect_ratio, S32 view_height_in_p
 	mPlaneCount(6),
 	mFrustumCornerDist(0.f)
 {
+	alignPlanes();
 	mAspect = llclamp(aspect_ratio, MIN_ASPECT_RATIO, MAX_ASPECT_RATIO);
 	mNearPlane = llclamp(near_plane, MIN_NEAR_PLANE, MAX_NEAR_PLANE);
 	if(far_plane < 0) far_plane = DEFAULT_FAR_PLANE;
@@ -67,6 +68,23 @@ LLCamera::LLCamera(F32 vertical_fov_rads, F32 aspect_ratio, S32 view_height_in_p
 	setView(vertical_fov_rads);
 } 
 
+LLCamera::~LLCamera()
+{
+
+}
+
+const LLCamera& LLCamera::operator=(const LLCamera& rhs)
+{
+	memcpy(this, &rhs, sizeof(LLCamera));
+	alignPlanes();
+	LLVector4a::memcpyNonAliased16((F32*) mAgentPlanes, (F32*) rhs.mAgentPlanes, 4*7);
+	return *this;
+}
+
+void LLCamera::alignPlanes()
+{
+	mAgentPlanes = (LLPlane*) LL_NEXT_ALIGNED_ADDRESS<U8>(mAgentPlaneBuffer);
+}
 
 // ---------------- LLCamera::getFoo() member functions ----------------
 
@@ -91,8 +109,8 @@ F32 LLCamera::getMaxView() const
 void LLCamera::setUserClipPlane(LLPlane plane)
 {
 	mPlaneCount = 7;
-	mAgentPlanes[6].p = plane;
-	mAgentPlanes[6].mask = calcPlaneMask(plane);
+	mAgentPlanes[6] = plane;
+	mPlaneMask[6] = calcPlaneMask(plane);
 }
 
 void LLCamera::disableUserClipPlane()
@@ -164,129 +182,66 @@ size_t LLCamera::readFrustumFromBuffer(const char *buffer)
 
 // ---------------- test methods  ---------------- 
 
-S32 LLCamera::AABBInFrustum(const LLVector3 &center, const LLVector3& radius) 
-{
-	static const LLVector3 scaler[] = {
-		LLVector3(-1,-1,-1),
-		LLVector3( 1,-1,-1),
-		LLVector3(-1, 1,-1),
-		LLVector3( 1, 1,-1),
-		LLVector3(-1,-1, 1),
-		LLVector3( 1,-1, 1),
-		LLVector3(-1, 1, 1),
-		LLVector3( 1, 1, 1)
+S32 LLCamera::AABBInFrustum(const LLVector4a &center, const LLVector4a& radius) 
+{
+	static const LLVector4a scaler[] = {
+		LLVector4a(-1,-1,-1),
+		LLVector4a( 1,-1,-1),
+		LLVector4a(-1, 1,-1),
+		LLVector4a( 1, 1,-1),
+		LLVector4a(-1,-1, 1),
+		LLVector4a( 1,-1, 1),
+		LLVector4a(-1, 1, 1),
+		LLVector4a( 1, 1, 1)
 	};
 
 	U8 mask = 0;
 	S32 result = 2;
 
-	/*if (mFrustumCornerDist > 0.f && radius.magVecSquared() > mFrustumCornerDist * mFrustumCornerDist)
-	{ //box is larger than frustum, check frustum quads against box planes
-
-		static const LLVector3 dir[] = 
-		{
-			LLVector3(1, 0, 0),
-			LLVector3(-1, 0, 0),
-			LLVector3(0, 1, 0),
-			LLVector3(0, -1, 0),
-			LLVector3(0, 0, 1),
-			LLVector3(0, 0, -1)
-		};
-
-		U32 quads[] = 
+	for (U32 i = 0; i < mPlaneCount; i++)
+	{
+		mask = mPlaneMask[i];
+		if (mask == 0xff)
 		{
-			0, 1, 2, 3,
-			0, 1, 5, 4,
-			2, 3, 7, 6,
-			3, 0, 7, 4,
-			1, 2, 6, 4,
-			4, 5, 6, 7
-		};
-
-		result = 0;
-
-		BOOL total_inside = TRUE;
-		for (U32 i = 0; i < 6; i++)
-		{ 
-			LLVector3 p = center + radius.scaledVec(dir[i]);
-			F32 d = -p*dir[i];
-
-			for (U32 j = 0; j <	6; j++)
-			{ //for each quad
-				F32 dist = mAgentFrustum[quads[j*4+0]]*dir[i] + d;
-				if (dist > 0)
-				{ //at least one frustum point is outside the AABB
-					total_inside = FALSE;
-					for (U32 k = 1; k < 4; k++)
-					{ //for each other point on quad
-						if ( mAgentFrustum[quads[j*4+k]]*dir[i]+d  <= 0.f)
-						{ //quad is straddling some plane of AABB
-							return 1;
-						}
-					}
-				}
-				else
-				{
-					for (U32 k = 1; k < 4; k++)
-					{
-						if (mAgentFrustum[quads[j*4+k]]*dir[i]+d > 0.f)
-						{
-							return 1;
-						}
-					}
-				}
-			}
+			continue;
 		}
 
-		if (total_inside)
+		const LLPlane& p = mAgentPlanes[i];
+		const LLVector4a& n = reinterpret_cast<const LLVector4a&>(p);
+		float d = p.mV[3];
+		LLVector4a rscale;
+		rscale.setMul(radius, scaler[mask]);
+
+		LLVector4a minp, maxp;
+		minp.setSub(center, rscale);
+		maxp.setAdd(center, rscale);
+
+		if (n.dot3(minp) > -d) 
 		{
-			result = 1;
+			return 0;
 		}
-	}
-	else*/
-	{
-		for (U32 i = 0; i < mPlaneCount; i++)
+	
+		if (n.dot3(maxp) > -d)
 		{
-			mask = mAgentPlanes[i].mask;
-			if (mask == 0xff)
-			{
-				continue;
-			}
-			LLPlane p = mAgentPlanes[i].p;
-			LLVector3 n = LLVector3(p);
-			float d = p.mV[3];
-			LLVector3 rscale = radius.scaledVec(scaler[mask]);
-
-			LLVector3 minp = center - rscale;
-			LLVector3 maxp = center + rscale;
-
-			if (n * minp > -d) 
-			{
-				return 0;
-			}
-		
-			if (n * maxp > -d)
-			{
-				result = 1;
-			}
+			result = 1;
 		}
 	}
 
-	
 	return result;
 }
 
-S32 LLCamera::AABBInFrustumNoFarClip(const LLVector3 &center, const LLVector3& radius) 
-{
-	static const LLVector3 scaler[] = {
-		LLVector3(-1,-1,-1),
-		LLVector3( 1,-1,-1),
-		LLVector3(-1, 1,-1),
-		LLVector3( 1, 1,-1),
-		LLVector3(-1,-1, 1),
-		LLVector3( 1,-1, 1),
-		LLVector3(-1, 1, 1),
-		LLVector3( 1, 1, 1)
+
+S32 LLCamera::AABBInFrustumNoFarClip(const LLVector4a& center, const LLVector4a& radius) 
+{
+	static const LLVector4a scaler[] = {
+		LLVector4a(-1,-1,-1),
+		LLVector4a( 1,-1,-1),
+		LLVector4a(-1, 1,-1),
+		LLVector4a( 1, 1,-1),
+		LLVector4a(-1,-1, 1),
+		LLVector4a( 1,-1, 1),
+		LLVector4a(-1, 1, 1),
+		LLVector4a( 1, 1, 1)
 	};
 
 	U8 mask = 0;
@@ -299,25 +254,28 @@ S32 LLCamera::AABBInFrustumNoFarClip(const LLVector3 &center, const LLVector3& r
 			continue;
 		}
 
-		mask = mAgentPlanes[i].mask;
+		mask = mPlaneMask[i];
 		if (mask == 0xff)
 		{
 			continue;
 		}
-		LLPlane p = mAgentPlanes[i].p;
-		LLVector3 n = LLVector3(p);
+
+		const LLPlane& p = mAgentPlanes[i];
+		const LLVector4a& n = reinterpret_cast<const LLVector4a&>(p);
 		float d = p.mV[3];
-		LLVector3 rscale = radius.scaledVec(scaler[mask]);
+		LLVector4a rscale;
+		rscale.setMul(radius, scaler[mask]);
 
-		LLVector3 minp = center - rscale;
-		LLVector3 maxp = center + rscale;
+		LLVector4a minp, maxp;
+		minp.setSub(center, rscale);
+		maxp.setAdd(center, rscale);
 
-		if (n * minp > -d) 
+		if (n.dot3(minp) > -d) 
 		{
 			return 0;
 		}
 	
-		if (n * maxp > -d)
+		if (n.dot3(maxp) > -d)
 		{
 			result = 1;
 		}
@@ -447,12 +405,12 @@ int LLCamera::sphereInFrustum(const LLVector3 &sphere_center, const F32 radius)
 	int res = 2;
 	for (int i = 0; i < 6; i++)
 	{
-		if (mAgentPlanes[i].mask == 0xff)
+		if (mPlaneMask[i] == 0xff)
 		{
 			continue;
 		}
 
-		float d = mAgentPlanes[i].p.dist(sphere_center);
+		float d = mAgentPlanes[i].dist(sphere_center);
 
 		if (d > radius) 
 		{
@@ -644,12 +602,14 @@ void LLCamera::ignoreAgentFrustumPlane(S32 idx)
 		return;
 	}
 
-	mAgentPlanes[idx].mask = 0xff;
-	mAgentPlanes[idx].p.clearVec();
+	mPlaneMask[idx] = 0xff;
+	mAgentPlanes[idx].clearVec();
 }
 
 void LLCamera::calcAgentFrustumPlanes(LLVector3* frust)
 {
+	alignPlanes();
+
 	for (int i = 0; i < 8; i++)
 	{
 		mAgentFrustum[i] = frust[i];
@@ -662,27 +622,27 @@ void LLCamera::calcAgentFrustumPlanes(LLVector3* frust)
 	//order of planes is important, keep most likely to fail in the front of the list
 
 	//near - frust[0], frust[1], frust[2]
-	mAgentPlanes[2].p = planeFromPoints(frust[0], frust[1], frust[2]);
+	mAgentPlanes[2] = planeFromPoints(frust[0], frust[1], frust[2]);
 
 	//far  
-	mAgentPlanes[5].p = planeFromPoints(frust[5], frust[4], frust[6]);
+	mAgentPlanes[5] = planeFromPoints(frust[5], frust[4], frust[6]);
 
 	//left  
-	mAgentPlanes[0].p = planeFromPoints(frust[4], frust[0], frust[7]);
+	mAgentPlanes[0] = planeFromPoints(frust[4], frust[0], frust[7]);
 
 	//right  
-	mAgentPlanes[1].p = planeFromPoints(frust[1], frust[5], frust[6]);
+	mAgentPlanes[1] = planeFromPoints(frust[1], frust[5], frust[6]);
 
 	//top  
-	mAgentPlanes[4].p = planeFromPoints(frust[3], frust[2], frust[6]);
+	mAgentPlanes[4] = planeFromPoints(frust[3], frust[2], frust[6]);
 
 	//bottom  
-	mAgentPlanes[3].p = planeFromPoints(frust[1], frust[0], frust[4]);
+	mAgentPlanes[3] = planeFromPoints(frust[1], frust[0], frust[4]);
 
 	//cache plane octant facing mask for use in AABBInFrustum
 	for (U32 i = 0; i < mPlaneCount; i++)
 	{
-		mAgentPlanes[i].mask = calcPlaneMask(mAgentPlanes[i].p);
+		mPlaneMask[i] = calcPlaneMask(mAgentPlanes[i]);
 	}
 }
 
diff --git a/indra/llmath/llcamera.h b/indra/llmath/llcamera.h
index d6c5f7bbb1..c40e819dcf 100644
--- a/indra/llmath/llcamera.h
+++ b/indra/llmath/llcamera.h
@@ -37,6 +37,7 @@
 #include "llmath.h"
 #include "llcoordframe.h"
 #include "llplane.h"
+#include "llvector4a.h"
 
 const F32 DEFAULT_FIELD_OF_VIEW 	= 60.f * DEG_TO_RAD;
 const F32 DEFAULT_ASPECT_RATIO 		= 640.f / 480.f;
@@ -79,6 +80,14 @@ class LLCamera
 : 	public LLCoordFrame
 {
 public:
+	
+	LLCamera(const LLCamera& rhs)
+	{
+		*this = rhs;
+	}
+
+	const LLCamera& operator=(const LLCamera& rhs);
+	
 	enum {
 		PLANE_LEFT = 0,
 		PLANE_RIGHT = 1,
@@ -129,13 +138,9 @@ private:
 	LLPlane mWorldPlanes[PLANE_NUM];
 	LLPlane mHorizPlanes[HORIZ_PLANE_NUM];
 
-	struct frustum_plane
-	{
-		frustum_plane() : mask(0) {}
-		LLPlane p;
-		U8 mask;
-	};
-	frustum_plane mAgentPlanes[7];  //frustum planes in agent space a la gluUnproject (I'm a bastard, I know) - DaveP
+	LLPlane* mAgentPlanes;  //frustum planes in agent space a la gluUnproject (I'm a bastard, I know) - DaveP
+	U8 mAgentPlaneBuffer[sizeof(LLPlane)*8];
+	U8 mPlaneMask[7];
 
 	U32 mPlaneCount;  //defaults to 6, if setUserClipPlane is called, uses user supplied clip plane in
 
@@ -143,12 +148,14 @@ private:
 public:
 	LLVector3 mAgentFrustum[8];  //8 corners of 6-plane frustum
 	F32	mFrustumCornerDist;		//distance to corner of frustum against far clip plane
-	LLPlane& getAgentPlane(U32 idx) { return mAgentPlanes[idx].p; }
+	LLPlane& getAgentPlane(U32 idx) { return mAgentPlanes[idx]; }
 
 public:
 	LLCamera();
 	LLCamera(F32 vertical_fov_rads, F32 aspect_ratio, S32 view_height_in_pixels, F32 near_plane, F32 far_plane);
-	virtual ~LLCamera(){} // no-op virtual destructor
+	virtual ~LLCamera();
+	
+	void alignPlanes();
 
 	void setUserClipPlane(LLPlane plane);
 	void disableUserClipPlane();
@@ -199,8 +206,8 @@ public:
 	S32 sphereInFrustum(const LLVector3 &center, const F32 radius) const;
 	S32 pointInFrustum(const LLVector3 &point) const { return sphereInFrustum(point, 0.0f); }
 	S32 sphereInFrustumFull(const LLVector3 &center, const F32 radius) const { return sphereInFrustum(center, radius); }
-	S32 AABBInFrustum(const LLVector3 &center, const LLVector3& radius);
-	S32 AABBInFrustumNoFarClip(const LLVector3 &center, const LLVector3& radius);
+	S32 AABBInFrustum(const LLVector4a& center, const LLVector4a& radius);
+	S32 AABBInFrustumNoFarClip(const LLVector4a& center, const LLVector4a& radius);
 
 	//does a quick 'n dirty sphere-sphere check
 	S32 sphereInFrustumQuick(const LLVector3 &sphere_center, const F32 radius); 
diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index 2f34fb1bb0..ae2259dba0 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -35,6 +35,7 @@
 
 #include "lltreenode.h"
 #include "v3math.h"
+#include "llvector4a.h"
 #include <vector>
 #include <set>
 
@@ -44,7 +45,7 @@
 #define OCT_ERRS LL_WARNS("OctreeErrors")
 #endif
 
-#define LL_OCTREE_PARANOIA_CHECK 0
+#define LL_OCTREE_PARANOIA_CHECK 1
 #if LL_DARWIN
 #define LL_OCTREE_MAX_CAPACITY 32
 #else
@@ -73,6 +74,13 @@ public:
 };
 
 template <class T>
+class LLOctreeTravelerDepthFirst : public LLOctreeTraveler<T>
+{
+public:
+	virtual void traverse(const LLOctreeNode<T>* node);
+};
+
+template <class T>
 class LLOctreeNode : public LLTreeNode<T>
 {
 public:
@@ -87,23 +95,22 @@ public:
 	typedef LLOctreeNode<T>		oct_node;
 	typedef LLOctreeListener<T>	oct_listener;
 
-	static const U8 OCTANT_POSITIVE_X = 0x01;
-	static const U8 OCTANT_POSITIVE_Y = 0x02;
-	static const U8 OCTANT_POSITIVE_Z = 0x04;
-		
-	LLOctreeNode(	LLVector3d center, 
-					LLVector3d size, 
+	LLOctreeNode(	const LLVector4a& center, 
+					const LLVector4a& size, 
 					BaseType* parent, 
-					U8 octant = 255)
+					S32 octant = -1)
 	:	mParent((oct_node*)parent), 
-		mCenter(center), 
-		mSize(size), 
 		mOctant(octant) 
 	{ 
+		mD = (LLVector4a*) _mm_malloc(sizeof(LLVector4a)*4, 16);
+
+		mD[CENTER] = center;
+		mD[SIZE] = size;
+
 		updateMinMax();
-		if ((mOctant == 255) && mParent)
+		if ((mOctant == -1) && mParent)
 		{
-			mOctant = ((oct_node*) mParent)->getOctant(mCenter.mdV);
+			mOctant = ((oct_node*) mParent)->getOctant(mD[CENTER]);
 		}
 
 		clearChildren();
@@ -117,43 +124,30 @@ public:
 		{
 			delete getChild(i);
 		} 
+
+		_mm_free(mD);
 	}
 
 	inline const BaseType* getParent()	const			{ return mParent; }
-	inline void setParent(BaseType* parent)			{ mParent = (oct_node*) parent; }
-	inline const LLVector3d& getCenter() const			{ return mCenter; }
-	inline const LLVector3d& getSize() const			{ return mSize; }
-	inline void setCenter(LLVector3d center)			{ mCenter = center; }
-	inline void setSize(LLVector3d size)				{ mSize = size; }
-    inline oct_node* getNodeAt(T* data)				{ return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
-	inline U8 getOctant() const						{ return mOctant; }
-	inline void setOctant(U8 octant)					{ mOctant = octant; }
+	inline void setParent(BaseType* parent)				{ mParent = (oct_node*) parent; }
+	inline const LLVector4a& getCenter() const			{ return mD[CENTER]; }
+	inline const LLVector4a& getSize() const			{ return mD[SIZE]; }
+	inline void setCenter(const LLVector4a& center)		{ mD[CENTER] = center; }
+	inline void setSize(const LLVector4a& size)			{ mD[SIZE] = size; }
+    inline oct_node* getNodeAt(T* data)					{ return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
+	inline S32 getOctant() const						{ return mOctant; }
+	inline void setOctant(S32 octant)					{ mOctant = octant; }
 	inline const oct_node*	getOctParent() const		{ return (const oct_node*) getParent(); }
 	inline oct_node* getOctParent() 					{ return (oct_node*) getParent(); }
 	
-	U8 getOctant(const F64 pos[]) const	//get the octant pos is in
+	S32 getOctant(const LLVector4a& pos) const			//get the octant pos is in
 	{
-		U8 ret = 0;
-
-		if (pos[0] > mCenter.mdV[0])
-		{
-			ret |= OCTANT_POSITIVE_X;
-		}
-		if (pos[1] > mCenter.mdV[1])
-		{
-			ret |= OCTANT_POSITIVE_Y;
-		}
-		if (pos[2] > mCenter.mdV[2])
-		{
-			ret |= OCTANT_POSITIVE_Z;
-		}
-
-		return ret;
+		return pos.greaterThan4(mD[CENTER]).getComparisonMask() & 0x7;
 	}
 	
-	inline bool isInside(const LLVector3d& pos, const F64& rad) const
+	inline bool isInside(const LLVector4a& pos, const F32& rad) const
 	{
-		return rad <= mSize.mdV[0]*2.0 && isInside(pos); 
+		return rad <= mD[SIZE][0]*2.f && isInside(pos); 
 	}
 
 	inline bool isInside(T* data) const			
@@ -161,29 +155,27 @@ public:
 		return isInside(data->getPositionGroup(), data->getBinRadius());
 	}
 
-	bool isInside(const LLVector3d& pos) const
+	bool isInside(const LLVector4a& pos) const
 	{
-		const F64& x = pos.mdV[0];
-		const F64& y = pos.mdV[1];
-		const F64& z = pos.mdV[2];
-			
-		if (x > mMax.mdV[0] || x <= mMin.mdV[0] ||
-			y > mMax.mdV[1] || y <= mMin.mdV[1] ||
-			z > mMax.mdV[2] || z <= mMin.mdV[2])
+		S32 gt = pos.greaterThan4(mD[MAX]).getComparisonMask() & 0x7;
+		if (gt)
 		{
 			return false;
 		}
-		
+
+		S32 lt = pos.lessEqual4(mD[MIN]).getComparisonMask() & 0x7;
+		if (lt)
+		{
+			return false;
+		}
+				
 		return true;
 	}
 	
 	void updateMinMax()
 	{
-		for (U32 i = 0; i < 3; i++)
-		{
-			mMax.mdV[i] = mCenter.mdV[i] + mSize.mdV[i];
-			mMin.mdV[i] = mCenter.mdV[i] - mSize.mdV[i];
-		}
+		mD[MAX].setAdd(mD[CENTER], mD[SIZE]);
+		mD[MIN].setSub(mD[CENTER], mD[SIZE]);
 	}
 
 	inline oct_listener* getOctListener(U32 index) 
@@ -196,34 +188,34 @@ public:
 		return contains(xform->getBinRadius());
 	}
 
-	bool contains(F64 radius)
+	bool contains(F32 radius)
 	{
 		if (mParent == NULL)
 		{	//root node contains nothing
 			return false;
 		}
 
-		F64 size = mSize.mdV[0];
-		F64 p_size = size * 2.0;
+		F32 size = mD[SIZE][0];
+		F32 p_size = size * 2.f;
 
-		return (radius <= 0.001 && size <= 0.001) ||
+		return (radius <= 0.001f && size <= 0.001f) ||
 				(radius <= p_size && radius > size);
 	}
 
-	static void pushCenter(LLVector3d &center, const LLVector3d &size, const T* data)
+	static void pushCenter(LLVector4a &center, const LLVector4a &size, const T* data)
 	{
-		const LLVector3d& pos = data->getPositionGroup();
-		for (U32 i = 0; i < 3; i++)
-		{
-			if (pos.mdV[i] > center.mdV[i])
-			{
-				center.mdV[i] += size.mdV[i];
-			}
-			else 
-			{
-				center.mdV[i] -= size.mdV[i];
-			}
-		}
+		const LLVector4a& pos = data->getPositionGroup();
+
+		LLVector4a gt = pos.greaterThan4(center);
+
+		LLVector4a up;
+		up.mQ = _mm_and_ps(size.mQ, gt.mQ);
+
+		LLVector4a down;
+		down.mQ = _mm_andnot_ps(gt.mQ, size.mQ);
+
+		center.add(up);
+		center.sub(down);
 	}
 
 	void accept(oct_traveler* visitor)				{ visitor->visit(this); }
@@ -242,21 +234,21 @@ public:
 	void accept(tree_traveler* visitor) const		{ visitor->visit(this); }
 	void accept(oct_traveler* visitor) const		{ visitor->visit(this); }
 	
-	oct_node* getNodeAt(const LLVector3d& pos, const F64& rad)
+	oct_node* getNodeAt(const LLVector4a& pos, const F32& rad)
 	{ 
 		LLOctreeNode<T>* node = this;
 
 		if (node->isInside(pos, rad))
 		{		
 			//do a quick search by octant
-			U8 octant = node->getOctant(pos.mdV);
+			S32 octant = node->getOctant(pos);
 			BOOL keep_going = TRUE;
 
 			//traverse the tree until we find a node that has no node
 			//at the appropriate octant or is smaller than the object.  
 			//by definition, that node is the smallest node that contains 
 			// the data
-			while (keep_going && node->getSize().mdV[0] >= rad)
+			while (keep_going && node->getSize()[0] >= rad)
 			{	
 				keep_going = FALSE;
 				for (U32 i = 0; i < node->getChildCount() && !keep_going; i++)
@@ -264,7 +256,7 @@ public:
 					if (node->getChild(i)->getOctant() == octant)
 					{
 						node = node->getChild(i);
-						octant = node->getOctant(pos.mdV);
+						octant = node->getOctant(pos);
 						keep_going = TRUE;
 					}
 				}
@@ -282,7 +274,7 @@ public:
 	{
 		if (data == NULL)
 		{
-			//OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
+			OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
 			return false;
 		}
 		LLOctreeNode<T>* parent = getOctParent();
@@ -292,7 +284,7 @@ public:
 		{
 			if (getElementCount() < LL_OCTREE_MAX_CAPACITY &&
 				(contains(data->getBinRadius()) ||
-				(data->getBinRadius() > getSize().mdV[0] &&
+				(data->getBinRadius() > getSize()[0] &&
 				parent && parent->getElementCount() >= LL_OCTREE_MAX_CAPACITY))) 
 			{ //it belongs here
 #if LL_OCTREE_PARANOIA_CHECK
@@ -323,16 +315,22 @@ public:
 				}
 				
 				//it's here, but no kids are in the right place, make a new kid
-				LLVector3d center(getCenter());
-				LLVector3d size(getSize()*0.5);
+				LLVector4a center = getCenter();
+				LLVector4a size = getSize();
+				size.mul(0.5f);
 		        		
 				//push center in direction of data
 				LLOctreeNode<T>::pushCenter(center, size, data);
 
 				// handle case where floating point number gets too small
-				if( llabs(center.mdV[0] - getCenter().mdV[0]) < F_APPROXIMATELY_ZERO &&
-					llabs(center.mdV[1] - getCenter().mdV[1]) < F_APPROXIMATELY_ZERO &&
-					llabs(center.mdV[2] - getCenter().mdV[2]) < F_APPROXIMATELY_ZERO)
+				LLVector4a val;
+				val.setSub(center, getCenter());
+				val.setAbs(val);
+				LLVector4a app_zero;
+				app_zero.mQ = F_APPROXIMATELY_ZERO_4A;
+				S32 lt = val.lessThan4(app_zero).getComparisonMask() & 0x7;
+
+				if( lt == 0x7 )
 				{
 					mData.insert(data);
 					BaseType::insert(data);
@@ -350,7 +348,7 @@ public:
 				//make sure no existing node matches this position
 				for (U32 i = 0; i < getChildCount(); i++)
 				{
-					if (mChild[i]->getCenter() == center)
+					if (mChild[i]->getCenter().equal3(center))
 					{
 						OCT_ERRS << "Octree detected duplicate child center and gave up." << llendl;
 						return false;
@@ -368,7 +366,7 @@ public:
 		else 
 		{
 			//it's not in here, give it to the root
-			//OCT_ERRS << "Octree insertion failed, starting over from root!" << llendl;
+			OCT_ERRS << "Octree insertion failed, starting over from root!" << llendl;
 
 			oct_node* node = this;
 
@@ -475,13 +473,19 @@ public:
 	void addChild(oct_node* child, BOOL silent = FALSE) 
 	{
 #if LL_OCTREE_PARANOIA_CHECK
+
+		if (child->getSize().equal3(getSize()))
+		{
+			OCT_ERRS << "Child size is same as parent size!" << llendl;
+		}
+
 		for (U32 i = 0; i < getChildCount(); i++)
 		{
-			if(mChild[i]->getSize() != child->getSize()) 
+			if(!mChild[i]->getSize().equal3(child->getSize())) 
 			{
 				OCT_ERRS <<"Invalid octree child size." << llendl;
 			}
-			if (mChild[i]->getCenter() == child->getCenter())
+			if (mChild[i]->getCenter().equal3(child->getCenter()))
 			{
 				OCT_ERRS <<"Duplicate octree child position." << llendl;
 			}
@@ -506,7 +510,7 @@ public:
 		}
 	}
 
-	void removeChild(U8 index, BOOL destroy = FALSE)
+	void removeChild(S32 index, BOOL destroy = FALSE)
 	{
 		for (U32 i = 0; i < this->getListenerCount(); i++)
 		{
@@ -547,18 +551,26 @@ public:
 			}
 		}
 
-		//OCT_ERRS << "Octree failed to delete requested child." << llendl;
+		OCT_ERRS << "Octree failed to delete requested child." << llendl;
 	}
 
 protected:	
+	typedef enum
+	{
+		CENTER = 0,
+		SIZE = 1,
+		MAX = 2,
+		MIN = 3
+	} eDName;
+
+	LLVector4a* mD;
+	
+	oct_node* mParent;
+	S32 mOctant;
+
 	child_list mChild;
 	element_list mData;
-	oct_node* mParent;
-	LLVector3d mCenter;
-	LLVector3d mSize;
-	LLVector3d mMax;
-	LLVector3d mMin;
-	U8 mOctant;
+		
 };
 
 //just like a regular node, except it might expand on insert and compress on balance
@@ -569,9 +581,9 @@ public:
 	typedef LLOctreeNode<T>	BaseType;
 	typedef LLOctreeNode<T>		oct_node;
 
-	LLOctreeRoot(	LLVector3d center, 
-					LLVector3d size, 
-					BaseType* parent)
+	LLOctreeRoot(const LLVector4a& center, 
+				 const LLVector4a& size, 
+				 BaseType* parent)
 	:	BaseType(center, size, parent)
 	{
 	}
@@ -612,28 +624,33 @@ public:
 	{
 		if (data == NULL) 
 		{
-			//OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl;
+			OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl;
 			return false;
 		}
 		
 		if (data->getBinRadius() > 4096.0)
 		{
-			//OCT_ERRS << "!!! ELEMENT EXCEEDS MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl;
+			OCT_ERRS << "!!! ELEMENT EXCEEDS MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl;
 			return false;
 		}
 		
-		const F64 MAX_MAG = 1024.0*1024.0;
+		LLVector4a MAX_MAG;
+		MAX_MAG.splat(1024.f*1024.f);
+
+		const LLVector4a& v = data->getPositionGroup();
+
+		LLVector4a val;
+		val.setSub(v, mD[CENTER]);
+		val.setAbs(val);
+		S32 lt = val.lessThan4(MAX_MAG).getComparisonMask() & 0x7;
 
-		const LLVector3d& v = data->getPositionGroup();
-		if (!(fabs(v.mdV[0]-this->mCenter.mdV[0]) < MAX_MAG &&
-		      fabs(v.mdV[1]-this->mCenter.mdV[1]) < MAX_MAG &&
-		      fabs(v.mdV[2]-this->mCenter.mdV[2]) < MAX_MAG))
+		if (lt != 0x7)
 		{
-			//OCT_ERRS << "!!! ELEMENT EXCEEDS RANGE OF SPATIAL PARTITION !!!" << llendl;
+			OCT_ERRS << "!!! ELEMENT EXCEEDS RANGE OF SPATIAL PARTITION !!!" << llendl;
 			return false;
 		}
 
-		if (this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup()))
+		if (this->getSize()[0] > data->getBinRadius() && isInside(data->getPositionGroup()))
 		{
 			//we got it, just act like a branch
 			oct_node* node = getNodeAt(data);
@@ -649,31 +666,34 @@ public:
 		else if (this->getChildCount() == 0)
 		{
 			//first object being added, just wrap it up
-			while (!(this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
+			while (!(this->getSize()[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
 			{
-				LLVector3d center, size;
+				LLVector4a center, size;
 				center = this->getCenter();
 				size = this->getSize();
 				LLOctreeNode<T>::pushCenter(center, size, data);
 				this->setCenter(center);
-				this->setSize(size*2);
+				size.mul(2.f);
+				this->setSize(size);
 				this->updateMinMax();
 			}
 			LLOctreeNode<T>::insert(data);
 		}
 		else
 		{
-			while (!(this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
+			while (!(this->getSize()[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
 			{
 				//the data is outside the root node, we need to grow
-				LLVector3d center(this->getCenter());
-				LLVector3d size(this->getSize());
+				LLVector4a center(this->getCenter());
+				LLVector4a size(this->getSize());
 
 				//expand this node
-				LLVector3d newcenter(center);
+				LLVector4a newcenter(center);
 				LLOctreeNode<T>::pushCenter(newcenter, size, data);
 				this->setCenter(newcenter);
-				this->setSize(size*2);
+				LLVector4a size2 = size;
+				size2.mul(2.f);
+				this->setSize(size2);
 				this->updateMinMax();
 
 				//copy our children to a new branch
@@ -710,4 +730,15 @@ void LLOctreeTraveler<T>::traverse(const LLOctreeNode<T>* node)
 		traverse(node->getChild(i));
 	}
 }
+
+template <class T>
+void LLOctreeTravelerDepthFirst<T>::traverse(const LLOctreeNode<T>* node)
+{
+	for (U32 i = 0; i < node->getChildCount(); i++)
+	{
+		traverse(node->getChild(i));
+	}
+	node->accept(this);
+}
+
 #endif
diff --git a/indra/llmath/lltreenode.h b/indra/llmath/lltreenode.h
index ee9836241a..e6d2521b2a 100644
--- a/indra/llmath/lltreenode.h
+++ b/indra/llmath/lltreenode.h
@@ -34,6 +34,9 @@
 
 #include "stdtypes.h"
 #include "xform.h"
+#include "llpointer.h"
+#include "llrefcount.h"
+
 #include <vector>
 
 template <class T> class LLTreeNode;
diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index 9b6e2488e6..72833c019f 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -45,8 +45,10 @@
 #include "m4math.h"
 #include "m3math.h"
 #include "llmatrix4a.h"
+#include "lloctree.h"
 #include "lldarray.h"
 #include "llvolume.h"
+#include "llvolumeoctree.h"
 #include "llstl.h"
 #include "llsdserialize.h"
 #include "llvector4a.h"
@@ -133,21 +135,20 @@ BOOL LLLineSegmentBoxIntersect(const F32* start, const F32* end, const F32* cent
 }
 
 
+
 // intersect test between triangle vert0, vert1, vert2 and a ray from orig in direction dir.
 // returns TRUE if intersecting and returns barycentric coordinates in intersection_a, intersection_b,
 // and returns the intersection point along dir in intersection_t.
 
 // Moller-Trumbore algorithm
 BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
-							F32* intersection_a, F32* intersection_b, F32* intersection_t, BOOL two_sided)
+							F32& intersection_a, F32& intersection_b, F32& intersection_t)
 {
-	F32 u, v, t;
 	
 	/* find vectors for two edges sharing vert0 */
 	LLVector4a edge1;
 	edge1.setSub(vert1, vert0);
 	
-	
 	LLVector4a edge2;
 	edge2.setSub(vert2, vert0);
 
@@ -156,87 +157,116 @@ BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, co
 	pvec.setCross3(dir, edge2);
 
 	/* if determinant is near zero, ray lies in plane of triangle */
-	F32 det = edge1.dot3(pvec);
-
-	if (!two_sided)
+	LLVector4a det;
+	det.setAllDot3(edge1, pvec);
+	
+	if (det.greaterEqual4(LLVector4a::getApproximatelyZero()).getComparisonMask() & 0x7)
 	{
-		if (det < F_APPROXIMATELY_ZERO)
-		{
-			return FALSE;
-		}
-
 		/* calculate distance from vert0 to ray origin */
 		LLVector4a tvec;
 		tvec.setSub(orig, vert0);
 
 		/* calculate U parameter and test bounds */
-		u = tvec.dot3(pvec);	
+		LLVector4a u;
+		u.setAllDot3(tvec,pvec);
 
-		if (u < 0.f || u > det)
+		if ((u.greaterEqual4(LLVector4a::getZero()).getComparisonMask() & 0x7) &&
+			(u.lessEqual4(det).getComparisonMask() & 0x7))
 		{
-			return FALSE;
+			/* prepare to test V parameter */
+			LLVector4a qvec;
+			qvec.setCross3(tvec, edge1);
+			
+			/* calculate V parameter and test bounds */
+			LLVector4a v;
+			v.setAllDot3(dir, qvec);
+
+			
+			//if (!(v < 0.f || u + v > det))
+
+			LLVector4a sum_uv;
+			sum_uv.setAdd(u, v);
+
+			S32 v_gequal = v.greaterEqual4(LLVector4a::getZero()).getComparisonMask() & 0x7;
+			S32 sum_lequal = sum_uv.lessEqual4(det).getComparisonMask() & 0x7;
+
+			if (v_gequal  && sum_lequal)
+			{
+				/* calculate t, scale parameters, ray intersects triangle */
+				LLVector4a t;
+				t.setAllDot3(edge2,qvec);
+
+				t.div(det);
+				u.div(det);
+				v.div(det);
+				
+				intersection_a = u[0];
+				intersection_b = v[0];
+				intersection_t = t[0];
+				return TRUE;
+			}
 		}
-	
-		/* prepare to test V parameter */
-		LLVector4a qvec;
-		qvec.setCross3(tvec, edge1);
+	}
 		
-		/* calculate V parameter and test bounds */
-		v = dir.dot3(qvec);
-		if (v < 0.f || u + v > det)
-		{
-			return FALSE;
-		}
+	return FALSE;
+} 
 
-		/* calculate t, scale parameters, ray intersects triangle */
-		t = edge2.dot3(qvec);
-		F32 inv_det = 1.0 / det;
-		t *= inv_det;
-		u *= inv_det;
-		v *= inv_det;
-	}
+BOOL LLTriangleRayIntersectTwoSided(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
+							F32& intersection_a, F32& intersection_b, F32& intersection_t)
+{
+	F32 u, v, t;
 	
-	else // two sided
-			{
-		if (det > -F_APPROXIMATELY_ZERO && det < F_APPROXIMATELY_ZERO)
-				{
-			return FALSE;
-				}
-		F32 inv_det = 1.0 / det;
+	/* find vectors for two edges sharing vert0 */
+	LLVector4a edge1;
+	edge1.setSub(vert1, vert0);
+	
+	
+	LLVector4a edge2;
+	edge2.setSub(vert2, vert0);
 
-		/* calculate distance from vert0 to ray origin */
-		LLVector4a tvec;
-		tvec.setSub(orig, vert0);
-		
-		/* calculate U parameter and test bounds */
-		u = (tvec.dot3(pvec)) * inv_det;
-		if (u < 0.f || u > 1.f)
-		{
-			return FALSE;
-			}
+	/* begin calculating determinant - also used to calculate U parameter */
+	LLVector4a pvec;
+	pvec.setCross3(dir, edge2);
 
-		/* prepare to test V parameter */
-		LLVector4a qvec;
-		qvec.setSub(tvec, edge1);
-		
-		/* calculate V parameter and test bounds */
-		v = (dir.dot3(qvec)) * inv_det;
-		
-		if (v < 0.f || u + v > 1.f)
-		{
-			return FALSE;
-		}
+	/* if determinant is near zero, ray lies in plane of triangle */
+	F32 det = edge1.dot3(pvec);
 
-		/* calculate t, ray intersects triangle */
-		t = (edge2.dot3(qvec)) * inv_det;
+	
+	if (det > -F_APPROXIMATELY_ZERO && det < F_APPROXIMATELY_ZERO)
+	{
+		return FALSE;
+	}
+
+	F32 inv_det = 1.f / det;
+
+	/* calculate distance from vert0 to ray origin */
+	LLVector4a tvec;
+	tvec.setSub(orig, vert0);
+	
+	/* calculate U parameter and test bounds */
+	u = (tvec.dot3(pvec)) * inv_det;
+	if (u < 0.f || u > 1.f)
+	{
+		return FALSE;
+	}
+
+	/* prepare to test V parameter */
+	tvec.sub(edge1);
+		
+	/* calculate V parameter and test bounds */
+	v = (dir.dot3(tvec)) * inv_det;
+	
+	if (v < 0.f || u + v > 1.f)
+	{
+		return FALSE;
 	}
+
+	/* calculate t, ray intersects triangle */
+	t = (edge2.dot3(tvec)) * inv_det;
 	
-	if (intersection_a != NULL)
-		*intersection_a = u;
-	if (intersection_b != NULL)
-		*intersection_b = v;
-	if (intersection_t != NULL)
-		*intersection_t = t;
+	intersection_a = u;
+	intersection_b = v;
+	intersection_t = t;
 	
 	
 	return TRUE;
@@ -244,7 +274,7 @@ BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, co
 
 //helper for non-aligned vectors
 BOOL LLTriangleRayIntersect(const LLVector3& vert0, const LLVector3& vert1, const LLVector3& vert2, const LLVector3& orig, const LLVector3& dir,
-							F32* intersection_a, F32* intersection_b, F32* intersection_t, BOOL two_sided)
+							F32& intersection_a, F32& intersection_b, F32& intersection_t, BOOL two_sided)
 {
 	LLVector4a vert0a, vert1a, vert2a, origa, dira;
 	vert0a.load3(vert0.mV);
@@ -253,10 +283,91 @@ BOOL LLTriangleRayIntersect(const LLVector3& vert0, const LLVector3& vert1, cons
 	origa.load3(orig.mV);
 	dira.load3(dir.mV);
 
-	return LLTriangleRayIntersect(vert0a, vert1a, vert2a, origa, dira, 
-			intersection_a, intersection_b, intersection_t, two_sided);
+	if (two_sided)
+	{
+		return LLTriangleRayIntersectTwoSided(vert0a, vert1a, vert2a, origa, dira, 
+				intersection_a, intersection_b, intersection_t);
+	}
+	else
+	{
+		return LLTriangleRayIntersect(vert0a, vert1a, vert2a, origa, dira, 
+				intersection_a, intersection_b, intersection_t);
+	}
 }
 
+class LLVolumeOctreeRebound : public LLOctreeTravelerDepthFirst<LLVolumeTriangle>
+{
+public:
+	const LLVolumeFace* mFace;
+
+	LLVolumeOctreeRebound(const LLVolumeFace* face)
+	{
+		mFace = face;
+	}
+
+	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* branch)
+	{
+		LLVolumeOctreeListener* node = (LLVolumeOctreeListener*) branch->getListener(0);
+
+		LLVector4a& min = node->mExtents[0];
+		LLVector4a& max = node->mExtents[1];
+
+		if (branch->getElementCount() != 0)
+		{
+			const LLVolumeTriangle* tri = *(branch->getData().begin());
+						
+			min = *(tri->mV[0]);
+			max = *(tri->mV[0]);
+			
+			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
+				branch->getData().begin(); iter != branch->getData().end(); ++iter)
+			{
+				//stretch by triangles in node
+				tri = *iter;
+				
+				min.setMin(*tri->mV[0]);
+				min.setMin(*tri->mV[1]);
+				min.setMin(*tri->mV[2]);
+
+				max.setMax(*tri->mV[0]);
+				max.setMax(*tri->mV[1]);
+				max.setMax(*tri->mV[2]);
+			}
+
+			for (S32 i = 0; i < branch->getChildCount(); ++i)
+			{  //stretch by child extents
+				LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(i)->getListener(0);
+				min.setMin(child->mExtents[0]);
+				max.setMax(child->mExtents[1]);
+			}
+		}
+		else if (branch->getChildCount() != 0)
+		{
+			LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(0)->getListener(0);
+
+			min = child->mExtents[0];
+			max = child->mExtents[1];
+
+			for (S32 i = 1; i < branch->getChildCount(); ++i)
+			{  //stretch by child extents
+				child = (LLVolumeOctreeListener*) branch->getChild(i)->getListener(0);
+				min.setMin(child->mExtents[0]);
+				max.setMax(child->mExtents[1]);
+			}
+		}
+		else
+		{
+			llerrs << "WTF? Empty leaf" << llendl;
+		}
+		
+		node->mBounds[0].setAdd(min, max);
+		node->mBounds[0].mul(0.5f);
+
+		node->mBounds[1].setSub(max,min);
+		node->mBounds[1].mul(0.5f);
+	}
+};
+
 
 //-------------------------------------------------------------------
 // statics
@@ -4244,6 +4355,7 @@ S32 LLVolume::lineSegmentIntersect(const LLVector3& start, const LLVector3& end,
 
 }
 
+
 S32 LLVolume::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end, 
 								   S32 face,
 								   LLVector3* intersection,LLVector2* tex_coord, LLVector3* normal, LLVector3* bi_normal)
@@ -4282,72 +4394,25 @@ S32 LLVolume::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& en
 		LLVector4a box_size;
 		box_size.setSub(face.mExtents[1], face.mExtents[0]);
 
-        if (LLLineSegmentBoxIntersect(start.getF32(), end.getF32(), box_center.getF32(), box_size.getF32()))
+        if (LLLineSegmentBoxIntersect(start, end, box_center, box_size))
 		{
 			if (bi_normal != NULL) // if the caller wants binormals, we may need to generate them
 			{
 				genBinormals(i);
 			}
-			
-			LLVector4a* p = (LLVector4a*) face.mPositions;
 
-			for (U32 tri = 0; tri < face.mNumIndices/3; tri++) 
+			if (!face.mOctree)
 			{
-				S32 index1 = face.mIndices[tri*3+0];
-				S32 index2 = face.mIndices[tri*3+1];
-				S32 index3 = face.mIndices[tri*3+2];
-
-				F32 a, b, t;
+				face.createOctree();
+			}
 			
-				if (LLTriangleRayIntersect(p[index1],
-					p[index2],
-					p[index3],
-					start, dir, &a, &b, &t, FALSE))
-				{
-					if ((t >= 0.f) &&      // if hit is after start
-						(t <= 1.f) &&      // and before end
-						(t < closest_t))   // and this hit is closer
-					{
-						closest_t = t;
-						hit_face = i;
-
-						if (intersection != NULL)
-						{
-							LLVector4a intersect = dir;
-							intersect.mul(closest_t);
-							intersect.add(start);
-							intersection->set(intersect.getF32());
-						}
-
-
-						if (tex_coord != NULL)
-						{
-							LLVector2* tc = (LLVector2*) face.mTexCoords;
-							*tex_coord = ((1.f - a - b)  * tc[index1] +
-								a              * tc[index2] +
-								b              * tc[index3]);
-
-						}
-
-						if (normal != NULL)
-						{
-							LLVector4* norm = (LLVector4*) face.mNormals;
-
-							*normal    = ((1.f - a - b)  * LLVector3(norm[index1]) + 
-								a              * LLVector3(norm[index2]) +
-								b              * LLVector3(norm[index3]));
-						}
-
-						if (bi_normal != NULL)
-						{
-							LLVector4* binormal = (LLVector4*) face.mBinormals;
-							*bi_normal = ((1.f - a - b)  * LLVector3(binormal[index1]) + 
-									a              * LLVector3(binormal[index2]) +
-									b              * LLVector3(binormal[index3]));
-						}
+			LLVector4a* p = (LLVector4a*) face.mPositions;
 
-					}
-				}
+			LLOctreeTriangleRayIntersect intersect(start, dir, &face, &closest_t, intersection, tex_coord, normal, bi_normal);
+			intersect.traverse(face.mOctree);
+			if (intersect.mHitFace)
+			{
+				hit_face = i;
 			}
 		}		
 	}
@@ -5128,13 +5193,29 @@ LLVolumeFace::LLVolumeFace() :
 	mBinormals(NULL),
 	mTexCoords(NULL),
 	mIndices(NULL),
-	mWeights(NULL)
+	mWeights(NULL),
+	mOctree(NULL)
 {
 	mExtents = (LLVector4a*) _mm_malloc(48, 16);
 	mCenter = mExtents+2;
 }
 
 LLVolumeFace::LLVolumeFace(const LLVolumeFace& src)
+:	mID(0),
+	mTypeMask(0),
+	mBeginS(0),
+	mBeginT(0),
+	mNumS(0),
+	mNumT(0),
+	mNumVertices(0),
+	mNumIndices(0),
+	mPositions(NULL),
+	mNormals(NULL),
+	mBinormals(NULL),
+	mTexCoords(NULL),
+	mIndices(NULL),
+	mWeights(NULL),
+	mOctree(NULL)
 { 
 	mExtents = (LLVector4a*) _mm_malloc(48, 16);
 	mCenter = mExtents+2;
@@ -5157,13 +5238,9 @@ LLVolumeFace& LLVolumeFace::operator=(const LLVolumeFace& src)
 
 	mNumVertices = 0;
 	mNumIndices = 0;
-	mPositions = NULL;
-	mNormals = NULL;
-	mBinormals = NULL;
-	mTexCoords = NULL;
-	mWeights = NULL;
-	mIndices = NULL;
 
+	freeData();
+	
 	LLVector4a::memcpyNonAliased16((F32*) mExtents, (F32*) src.mExtents, 12);
 
 	resizeVertices(src.mNumVertices);
@@ -5179,6 +5256,7 @@ LLVolumeFace& LLVolumeFace::operator=(const LLVolumeFace& src)
 		LLVector4a::memcpyNonAliased16((F32*) mNormals, (F32*) src.mNormals, vert_size);
 		LLVector4a::memcpyNonAliased16((F32*) mTexCoords, (F32*) src.mTexCoords, vert_size);
 
+
 		if (src.mBinormals)
 		{
 			allocateBinormals(src.mNumVertices);
@@ -5217,17 +5295,37 @@ LLVolumeFace& LLVolumeFace::operator=(const LLVolumeFace& src)
 
 LLVolumeFace::~LLVolumeFace()
 {
+	_mm_free(mExtents);
+	mExtents = NULL;
+
+	freeData();
+}
+
+void LLVolumeFace::freeData()
+{
 	_mm_free(mPositions);
+	mPositions = NULL;
 	_mm_free(mNormals);
+	mNormals = NULL;
 	_mm_free(mTexCoords);
+	mTexCoords = NULL;
 	_mm_free(mIndices);
+	mIndices = NULL;
 	_mm_free(mBinormals);
+	mBinormals = NULL;
 	_mm_free(mWeights);
-	_mm_free(mExtents);
+	mWeights = NULL;
+
+	delete mOctree;
+	mOctree = NULL;
 }
 
 BOOL LLVolumeFace::create(LLVolume* volume, BOOL partial_build)
 {
+	//tree for this face is no longer valid
+	delete mOctree;
+	mOctree = NULL;
+
 	if (mTypeMask & CAP_MASK)
 	{
 		return createCap(volume, partial_build);
@@ -5250,6 +5348,18 @@ void LLVolumeFace::getVertexData(U16 index, LLVolumeFace::VertexData& cv)
 	cv.mTexCoord = mTexCoords[index];
 }
 
+bool LLVolumeFace::VertexMapData::operator==(const LLVolumeFace::VertexData& rhs) const
+{
+	return getPosition().equal3(rhs.getPosition()) &&
+		mTexCoord == rhs.mTexCoord &&
+		getNormal().equal3(rhs.getNormal());
+}
+
+bool LLVolumeFace::VertexMapData::ComparePosition::operator()(const LLVector4a& a, const LLVector4a& b) const
+{
+	return a.less3(b);			
+}
+
 void LLVolumeFace::optimize(F32 angle_cutoff)
 {
 	LLVolumeFace new_face;
@@ -5305,6 +5415,60 @@ void LLVolumeFace::optimize(F32 angle_cutoff)
 	swapData(new_face);
 }
 
+
+void LLVolumeFace::createOctree()
+{
+	LLVector4a center;
+	LLVector4a size;
+	center.splat(0.f);
+	size.splat(1.f);
+
+	mOctree = new LLOctreeRoot<LLVolumeTriangle>(center, size, NULL);
+	new LLVolumeOctreeListener(mOctree);
+
+	for (U32 i = 0; i < mNumIndices; i+= 3)
+	{
+		LLPointer<LLVolumeTriangle> tri = new LLVolumeTriangle();
+				
+		const LLVector4a& v0 = mPositions[mIndices[i]];
+		const LLVector4a& v1 = mPositions[mIndices[i+1]];
+		const LLVector4a& v2 = mPositions[mIndices[i+2]];
+
+		tri->mV[0] = &v0;
+		tri->mV[1] = &v1;
+		tri->mV[2] = &v2;
+
+		tri->mIndex[0] = mIndices[i];
+		tri->mIndex[1] = mIndices[i+1];
+		tri->mIndex[2] = mIndices[i+2];
+
+		LLVector4a min = v0;
+		min.setMin(v1);
+		min.setMin(v2);
+
+		LLVector4a max = v0;
+		max.setMax(v1);
+		max.setMax(v2);
+
+		LLVector4a center;
+		center.setAdd(min, max);
+		center.mul(0.5f);
+
+		*tri->mPositionGroup = center;
+
+		LLVector4a size;
+		size.setSub(max,min);
+		
+		tri->mRadius = size.length3() * 0.5f;
+		
+		mOctree->insert(tri);
+	}
+
+	LLVolumeOctreeRebound rebound(this);
+	rebound.traverse(mOctree);
+}
+
+
 void LLVolumeFace::swapData(LLVolumeFace& rhs)
 {
 	llswap(rhs.mPositions, mPositions);
diff --git a/indra/llmath/llvolume.h b/indra/llmath/llvolume.h
index 7c63266aab..c49d1c650d 100644
--- a/indra/llmath/llvolume.h
+++ b/indra/llmath/llvolume.h
@@ -40,8 +40,13 @@ class LLPathParams;
 class LLVolumeParams;
 class LLProfile;
 class LLPath;
+
+template <class T> class LLOctreeNode;
+
+class LLVector4a;
 class LLVolumeFace;
 class LLVolume;
+class LLVolumeTriangle;
 
 #include "lldarray.h"
 #include "lluuid.h"
@@ -49,15 +54,14 @@ class LLVolume;
 //#include "vmath.h"
 #include "v2math.h"
 #include "v3math.h"
+#include "v3dmath.h"
 #include "v4math.h"
-#include "llvector4a.h"
 #include "llquaternion.h"
 #include "llstrider.h"
 #include "v4coloru.h"
 #include "llrefcount.h"
 #include "llfile.h"
 
-
 //============================================================================
 
 const S32 MIN_DETAIL_FACES = 6;
@@ -830,6 +834,9 @@ public:
 	LLVolumeFace& operator=(const LLVolumeFace& rhs);
 
 	~LLVolumeFace();
+private:
+	void freeData();
+public:
 
 	BOOL create(LLVolume* volume, BOOL partial_build = FALSE);
 	void createBinormals();
@@ -855,26 +862,19 @@ public:
 	public:
 		U16 mIndex;
 
-		bool operator==(const LLVolumeFace::VertexData& rhs) const
-		{
-			return getPosition().equal3(rhs.getPosition()) &&
-				mTexCoord == rhs.mTexCoord &&
-				getNormal().equal3(rhs.getNormal());
-		}
+		bool operator==(const LLVolumeFace::VertexData& rhs) const;
 
 		struct ComparePosition
 		{
-			bool operator()(const LLVector4a& a, const LLVector4a& b) const
-			{
-				return a.less3(b);			
-			}
+			bool operator()(const LLVector4a& a, const LLVector4a& b) const;
 		};
 
 		typedef std::map<LLVector4a, std::vector<VertexMapData>, VertexMapData::ComparePosition > PointMap;
 	};
 
 	void optimize(F32 angle_cutoff = 2.f);
-	
+	void createOctree();
+
 	enum
 	{
 		SINGLE_MASK =	0x0001,
@@ -919,6 +919,8 @@ public:
 	// mWeights.size() should be empty or match mVertices.size()  
 	LLVector4a* mWeights;
 
+	LLOctreeNode<LLVolumeTriangle>* mOctree;
+
 private:
 	BOOL createUnCutCubeCap(LLVolume* volume, BOOL partial_build = FALSE);
 	BOOL createCap(LLVolume* volume, BOOL partial_build = FALSE);
@@ -1082,12 +1084,15 @@ void calc_binormal_from_triangle(
 
 BOOL LLLineSegmentBoxIntersect(const F32* start, const F32* end, const F32* center, const F32* size);
 BOOL LLLineSegmentBoxIntersect(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& size);
+BOOL LLLineSegmentBoxIntersect(const LLVector4a& start, const LLVector4a& end, const LLVector4a& center, const LLVector4a& size);
 
 BOOL LLTriangleRayIntersect(const LLVector3& vert0, const LLVector3& vert1, const LLVector3& vert2, const LLVector3& orig, const LLVector3& dir,
-							F32* intersection_a, F32* intersection_b, F32* intersection_t, BOOL two_sided);
+							F32& intersection_a, F32& intersection_b, F32& intersection_t, BOOL two_sided);
 
 BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
-							F32* intersection_a, F32* intersection_b, F32* intersection_t, BOOL two_sided);
+							F32& intersection_a, F32& intersection_b, F32& intersection_t);
+BOOL LLTriangleRayIntersectTwoSided(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
+							F32& intersection_a, F32& intersection_b, F32& intersection_t);