Octree triven raycast works, time to profile.

7 files changed, 58 insertions, 206 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/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 d261811aa2..c4172de651 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -48,6 +48,7 @@
 #include "lloctree.h"
 #include "lldarray.h"
 #include "llvolume.h"
+#include "llvolumeoctree.h"
 #include "llstl.h"
 #include "llsdserialize.h"
 #include "llvector4a.h"
@@ -133,50 +134,6 @@ BOOL LLLineSegmentBoxIntersect(const F32* start, const F32* end, const F32* cent
 	return true;
 }
 
-BOOL LLLineSegmentBoxIntersect(const LLVector4a& start, const LLVector4a& end, const LLVector4a& center, const LLVector4a& size)
-{
-	LLVector4a fAWdU;
-	LLVector4a dir;
-	LLVector4a diff;
-
-	dir.setSub(end, start);
-	dir.mul(0.5f);
-
-	diff.setAdd(end,start);
-	diff.mul(0.5f);
-	diff.sub(center);
-	fAWdU.setAbs(dir); 
-
-	LLVector4a rhs;
-	rhs.setAdd(size, fAWdU);
-
-	LLVector4a lhs;
-	lhs.setAbs(diff);
-
-	S32 grt = lhs.greaterThan4(rhs).getComparisonMask();
-
-	if (grt & 0x7)
-	{
-		return false;
-	}
-	
-	LLVector4a f;
-	f.setCross3(dir, diff);
-	f.setAbs(f);
-
-	LLVector4a v0; v0.mQ = _mm_shuffle_ps(size.mQ, size.mQ, _MM_SHUFFLE(3,1,0,0));
-	LLVector4a v1; v1.mQ = _mm_shuffle_ps(fAWdU.mQ, fAWdU.mQ, _MM_SHUFFLE(3,2,2,1));
-	lhs.setMul(v0, v1);
-
-	v0.mQ = _mm_shuffle_ps(size.mQ, size.mQ, _MM_SHUFFLE(3,2,2,1));
-	v1.mQ = _mm_shuffle_ps(fAWdU.mQ, fAWdU.mQ, _MM_SHUFFLE(3,1,0,0));
-	rhs.setMul(v0, v1);
-	rhs.add(lhs);
-
-	grt = f.greaterThan4(rhs).getComparisonMask();
-
-	return (grt & 0x7) ? false : true;	
-}
 
 
 // intersect test between triangle vert0, vert1, vert2 and a ray from orig in direction dir.
@@ -203,7 +160,7 @@ BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, co
 	LLVector4a det;
 	det.setAllDot3(edge1, pvec);
 	
-	if (det.greaterEqual4(LLVector4a::getApproximatelyZero()).getComparisonMask())
+	if (det.greaterEqual4(LLVector4a::getApproximatelyZero()).getComparisonMask() & 0x7)
 	{
 		/* calculate distance from vert0 to ray origin */
 		LLVector4a tvec;
@@ -213,8 +170,8 @@ BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, co
 		LLVector4a u;
 		u.setAllDot3(tvec,pvec);
 
-		if (u.greaterEqual4(LLVector4a::getZero()).getComparisonMask() &&
-			u.lessEqual4(det).getComparisonMask())
+		if ((u.greaterEqual4(LLVector4a::getZero()).getComparisonMask() & 0x7) &&
+			(u.lessEqual4(det).getComparisonMask() & 0x7))
 		{
 			/* prepare to test V parameter */
 			LLVector4a qvec;
@@ -230,10 +187,10 @@ BOOL LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, co
 			LLVector4a sum_uv;
 			sum_uv.setAdd(u, v);
 
-			S32 v_gequal = v.greaterEqual4(LLVector4a::getZero()).getComparisonMask();
-			S32 sum_lequal = sum_uv.lessEqual4(det).getComparisonMask();
+			S32 v_gequal = v.greaterEqual4(LLVector4a::getZero()).getComparisonMask() & 0x7;
+			S32 sum_lequal = sum_uv.lessEqual4(det).getComparisonMask() & 0x7;
 
-			if (v_gequal && sum_lequal)
+			if (v_gequal  && sum_lequal)
 			{
 				/* calculate t, scale parameters, ray intersects triangle */
 				LLVector4a t;
@@ -338,44 +295,6 @@ BOOL LLTriangleRayIntersect(const LLVector3& vert0, const LLVector3& vert1, cons
 	}
 }
 
-
-class LLVolumeOctreeListener : public LLOctreeListener<LLVolumeFace::Triangle>
-{
-public:
-	
-	LLVolumeOctreeListener(LLOctreeNode<LLVolumeFace::Triangle>* node)
-	{
-		node->addListener(this);
-
-		mBounds = (LLVector4a*) _mm_malloc(sizeof(LLVector4a)*4, 16);
-		mExtents = mBounds+2;
-	}
-
-	~LLVolumeOctreeListener()
-	{
-		_mm_free(mBounds);
-	}
-	
-	 //LISTENER FUNCTIONS
-	virtual void handleChildAddition(const LLOctreeNode<LLVolumeFace::Triangle>* parent, 
-		LLOctreeNode<LLVolumeFace::Triangle>* child)
-	{
-		new LLVolumeOctreeListener(child);
-	}
-
-	virtual void handleStateChange(const LLTreeNode<LLVolumeFace::Triangle>* node) { }
-	virtual void handleChildRemoval(const LLOctreeNode<LLVolumeFace::Triangle>* parent, 
-			const LLOctreeNode<LLVolumeFace::Triangle>* child) {	}
-	virtual void handleInsertion(const LLTreeNode<LLVolumeFace::Triangle>* node, LLVolumeFace::Triangle* tri) { }
-	virtual void handleRemoval(const LLTreeNode<LLVolumeFace::Triangle>* node, LLVolumeFace::Triangle* tri) { }
-	virtual void handleDestruction(const LLTreeNode<LLVolumeFace::Triangle>* node) { }
-	
-
-public:
-	LLVector4a* mBounds; // bounding box (center, size) of this node and all its children (tight fit to objects)
-	LLVector4a* mExtents; // extents (min, max) of this node and all its children
-};
-
 class LLVolumeOctreeRebound : public LLOctreeTravelerDepthFirst<LLVolumeFace::Triangle>
 {
 public:
@@ -4436,113 +4355,6 @@ S32 LLVolume::lineSegmentIntersect(const LLVector3& start, const LLVector3& end,
 
 }
 
-class LLOctreeTriangleRayIntersect : public LLOctreeTraveler<LLVolumeFace::Triangle>
-{
-public:
-	const LLVolumeFace* mFace;
-	LLVector4a mStart;
-	LLVector4a mDir;
-	LLVector4a mEnd;
-	LLVector3* mIntersection;
-	LLVector2* mTexCoord;
-	LLVector3* mNormal;
-	LLVector3* mBinormal;
-	F32* mClosestT;
-	bool mHitFace;
-
-	LLOctreeTriangleRayIntersect(const LLVector4a& start, const LLVector4a& dir, 
-								   const LLVolumeFace* face, F32* closest_t,
-								   LLVector3* intersection,LLVector2* tex_coord, LLVector3* normal, LLVector3* bi_normal)
-								   : mFace(face),
-								     mStart(start),
-									 mDir(dir),
-									 mIntersection(intersection),
-									 mTexCoord(tex_coord),
-									 mNormal(normal),
-									 mBinormal(bi_normal),
-									 mClosestT(closest_t),
-									 mHitFace(false)
-	{
-		mEnd.setAdd(mStart, mDir);
-	}
-
-	void traverse(const LLOctreeNode<LLVolumeFace::Triangle>* node)
-	{
-		LLVolumeOctreeListener* vl = (LLVolumeOctreeListener*) node->getListener(0);
-
-		/*const F32* start = mStart.getF32();
-		const F32* end = mEnd.getF32();
-		const F32* center = vl->mBounds[0].getF32();
-		const F32* size = vl->mBounds[1].getF32();*/
-
-		if (LLLineSegmentBoxIntersect(mStart, mEnd, vl->mBounds[0], vl->mBounds[1]))
-		{
-			node->accept(this);
-			for (S32 i = 0; i < node->getChildCount(); ++i)
-			{
-				traverse(node->getChild(i));
-			}
-		}
-	}
-
-	void visit(const LLOctreeNode<LLVolumeFace::Triangle>* node)
-	{
-		for (LLOctreeNode<LLVolumeFace::Triangle>::const_element_iter iter = 
-				node->getData().begin(); iter != node->getData().end(); ++iter)
-		{
-			const LLVolumeFace::Triangle* tri = *iter;
-
-			F32 a, b, t;
-			
-			if (LLTriangleRayIntersect(*tri->mV[0], *tri->mV[1], *tri->mV[2],
-					mStart, mDir, a, b, t))
-			{
-				if ((t >= 0.f) &&      // if hit is after start
-					(t <= 1.f) &&      // and before end
-					(t < *mClosestT))   // and this hit is closer
-				{
-					*mClosestT = t;
-					mHitFace = true;
-
-					if (mIntersection != NULL)
-					{
-						LLVector4a intersect = mDir;
-						intersect.mul(*mClosestT);
-						intersect.add(mStart);
-						mIntersection->set(intersect.getF32());
-					}
-
-
-					if (mTexCoord != NULL)
-					{
-						LLVector2* tc = (LLVector2*) mFace->mTexCoords;
-						*mTexCoord = ((1.f - a - b)  * tc[tri->mIndex[0]] +
-							a              * tc[tri->mIndex[1]] +
-							b              * tc[tri->mIndex[2]]);
-
-					}
-
-					if (mNormal != NULL)
-					{
-						LLVector4* norm = (LLVector4*) mFace->mNormals;
-
-						*mNormal    = ((1.f - a - b)  * LLVector3(norm[tri->mIndex[0]]) + 
-							a              * LLVector3(norm[tri->mIndex[1]]) +
-							b              * LLVector3(norm[tri->mIndex[2]]));
-					}
-
-					if (mBinormal != NULL)
-					{
-						LLVector4* binormal = (LLVector4*) mFace->mBinormals;
-						*mBinormal = ((1.f - a - b)  * LLVector3(binormal[tri->mIndex[0]]) + 
-								a              * LLVector3(binormal[tri->mIndex[1]]) +
-								b              * LLVector3(binormal[tri->mIndex[2]]));
-					}
-				}
-			}
-		}
-	}
-};
 
 S32 LLVolume::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end, 
 								   S32 face,
diff --git a/indra/llmath/llvolume.h b/indra/llmath/llvolume.h
index a40a21b405..0ae8aa19ca 100644
--- a/indra/llmath/llvolume.h
+++ b/indra/llmath/llvolume.h
@@ -42,6 +42,7 @@ class LLProfile;
 class LLPath;
 
 template <class T> class LLOctreeNode;
+
 class LLVector4a;
 class LLVolumeFace;
 class LLVolume;
@@ -1095,6 +1096,7 @@ 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);
diff --git a/indra/newview/llspatialpartition.cpp b/indra/newview/llspatialpartition.cpp
index 60e704d360..355173772b 100644
--- a/indra/newview/llspatialpartition.cpp
+++ b/indra/newview/llspatialpartition.cpp
@@ -38,6 +38,7 @@
 #include "llviewerobjectlist.h"
 #include "llvovolume.h"
 #include "llvolume.h"
+#include "llvolumeoctree.h"
 #include "llviewercamera.h"
 #include "llface.h"
 #include "llviewercontrol.h"
@@ -2769,17 +2770,26 @@ void renderLights(LLDrawable* drawablep)
 	}
 }
 
-class LLRenderOctree : public LLOctreeTraveler<LLVolumeFace::Triangle>
+class LLRenderOctreeRaycast : public LLOctreeTriangleRayIntersect
 {
 public:
+	
+	LLRenderOctreeRaycast(const LLVector3& start, const LLVector3& end)
+	{
+		mStart.load3(start.mV);
+		mEnd.load3(end.mV);
+		mDir.setSub(mEnd, mStart);
+	}
+
 	void visit(const LLOctreeNode<LLVolumeFace::Triangle>* branch)
 	{
-		const LLVector3d& c = branch->getCenter();
-		const LLVector3d& s = branch->getSize();
+		LLVolumeOctreeListener* vl = (LLVolumeOctreeListener*) branch->getListener(0);
 
-		LLVector3 pos((F32) c.mdV[0], (F32) c.mdV[1], (F32) c.mdV[2]);
-		LLVector3 size((F32) s.mdV[0], (F32) s.mdV[1], (F32) s.mdV[2]);
-		drawBoxOutline(pos, size);
+		LLVector3 center, size;
+		center.set(vl->mBounds[0].getF32());
+		size.set(vl->mBounds[1].getF32());
+
+		drawBoxOutline(center, size);
 	}
 };
 
@@ -2813,7 +2823,11 @@ void renderRaycast(LLDrawable* drawablep)
 
 				gGL.pushMatrix();
 				glMultMatrixf((F32*) vobj->getRelativeXform().mMatrix);
-				LLRenderOctree render;
+				LLVector3 start, end;
+				start = vobj->agentPositionToVolume(gDebugRaycastStart);
+				end = vobj->agentPositionToVolume(gDebugRaycastEnd);
+
+				LLRenderOctreeRaycast render(start, end);
 				render.traverse(face.mOctree);
 				gGL.popMatrix();		
 			}
diff --git a/indra/newview/llviewerwindow.cpp b/indra/newview/llviewerwindow.cpp
index 2422995288..0564f02ce5 100644
--- a/indra/newview/llviewerwindow.cpp
+++ b/indra/newview/llviewerwindow.cpp
@@ -231,6 +231,8 @@ LLVector2       gDebugRaycastTexCoord;
 LLVector3       gDebugRaycastNormal;
 LLVector3       gDebugRaycastBinormal;
 S32				gDebugRaycastFaceHit;
+LLVector3		gDebugRaycastStart;
+LLVector3		gDebugRaycastEnd;
 
 // HUD display lines in lower right
 BOOL				gDisplayWindInfo = FALSE;
@@ -2529,7 +2531,9 @@ void LLViewerWindow::updateUI()
 											  &gDebugRaycastIntersection,
 											  &gDebugRaycastTexCoord,
 											  &gDebugRaycastNormal,
-											  &gDebugRaycastBinormal);
+											  &gDebugRaycastBinormal,
+											  &gDebugRaycastStart,
+											  &gDebugRaycastEnd);
 	}
 
 	updateMouseDelta();
@@ -3445,7 +3449,9 @@ LLViewerObject* LLViewerWindow::cursorIntersect(S32 mouse_x, S32 mouse_y, F32 de
 												LLVector3 *intersection,
 												LLVector2 *uv,
 												LLVector3 *normal,
-												LLVector3 *binormal)
+												LLVector3 *binormal,
+												LLVector3* start,
+												LLVector3* end)
 {
 	S32 x = mouse_x;
 	S32 y = mouse_y;
@@ -3477,7 +3483,16 @@ LLViewerObject* LLViewerWindow::cursorIntersect(S32 mouse_x, S32 mouse_y, F32 de
 	LLVector3 mouse_world_start = mouse_point_global;
 	LLVector3 mouse_world_end   = mouse_point_global + mouse_direction_global * depth;
 
-	
+	if (start)
+	{
+		*start = mouse_world_start;
+	}
+
+	if (end)
+	{
+		*end = mouse_world_end;
+	}
+
 	LLViewerObject* found = NULL;
 
 	if (this_object)  // check only this object
diff --git a/indra/newview/llviewerwindow.h b/indra/newview/llviewerwindow.h
index 410445d97f..156a1ff8ad 100644
--- a/indra/newview/llviewerwindow.h
+++ b/indra/newview/llviewerwindow.h
@@ -361,7 +361,9 @@ public:
 									LLVector3 *intersection = NULL,
 									LLVector2 *uv = NULL,
 									LLVector3 *normal = NULL,
-									LLVector3 *binormal = NULL);
+									LLVector3 *binormal = NULL,
+									LLVector3* start = NULL,
+									LLVector3* end = NULL);
 	
 	
 	// Returns a pointer to the last object hit
@@ -507,6 +509,8 @@ extern LLVector2        gDebugRaycastTexCoord;
 extern LLVector3        gDebugRaycastNormal;
 extern LLVector3        gDebugRaycastBinormal;
 extern S32				gDebugRaycastFaceHit;
+extern LLVector3		gDebugRaycastStart;
+extern LLVector3		gDebugRaycastEnd;
 
 extern S32 CHAT_BAR_HEIGHT;