Added test code for volume raycast octree and fixed a crash in render cost calculation when selecting trees/grass. Reviewed by jwolk.

5 files changed, 145 insertions, 38 deletions

diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index ab9f8c4c24..4798197921 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -94,6 +94,8 @@ const F32 SKEW_MAX	=  0.95f;
 const F32 SCULPT_MIN_AREA = 0.002f;
 const S32 SCULPT_MIN_AREA_DETAIL = 1;
 
+extern BOOL gDebugGL;
+
 BOOL check_same_clock_dir( const LLVector3& pt1, const LLVector3& pt2, const LLVector3& pt3, const LLVector3& norm)
 {    
 	LLVector3 test = (pt2-pt1)%(pt3-pt2);
@@ -308,22 +310,26 @@ public:
 	}
 
 	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* branch)
-	{
+	{ //this is a depth first traversal, so it's safe to assum all children have complete
+		//bounding data
+
 		LLVolumeOctreeListener* node = (LLVolumeOctreeListener*) branch->getListener(0);
 
 		LLVector4a& min = node->mExtents[0];
 		LLVector4a& max = node->mExtents[1];
 
-		if (branch->getElementCount() != 0)
-		{
+		if (!branch->getData().empty())
+		{ //node has data, find AABB that binds data set
 			const LLVolumeTriangle* tri = *(branch->getData().begin());
-						
+			
+			//initialize min/max to first available vertex
 			min = *(tri->mV[0]);
 			max = *(tri->mV[0]);
 			
 			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
 				branch->getData().begin(); iter != branch->getData().end(); ++iter)
-			{
+			{ //for each triangle in node
+
 				//stretch by triangles in node
 				tri = *iter;
 				
@@ -335,33 +341,27 @@ public:
 				max.setMax(max, *tri->mV[1]);
 				max.setMax(max, *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(min, child->mExtents[0]);
-				max.setMax(min, child->mExtents[1]);
-			}
 		}
-		else if (branch->getChildCount() != 0)
-		{
+		else if (!branch->getChildren().empty())
+		{ //no data, but child nodes exist
 			LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(0)->getListener(0);
 
+			//initialize min/max to extents of first child
 			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(min, child->mExtents[0]);
-				max.setMax(max, child->mExtents[1]);
-			}
 		}
 		else
 		{
 			llerrs << "WTF? Empty leaf" << llendl;
 		}
-		
+
+		for (S32 i = 0; i < branch->getChildCount(); ++i)
+		{  //stretch by child extents
+			LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(i)->getListener(0);
+			min.setMin(min, child->mExtents[0]);
+			max.setMax(max, child->mExtents[1]);
+		}
+
 		node->mBounds[0].setAdd(min, max);
 		node->mBounds[0].mul(0.5f);
 
@@ -370,7 +370,6 @@ public:
 	}
 };
 
-
 //-------------------------------------------------------------------
 // statics
 //-------------------------------------------------------------------
@@ -5474,45 +5473,59 @@ void LLVolumeFace::createOctree()
 	new LLVolumeOctreeListener(mOctree);
 
 	for (U32 i = 0; i < mNumIndices; i+= 3)
-	{
+	{ //for each triangle
 		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]];
 
+		//store pointers to vertex data
 		tri->mV[0] = &v0;
 		tri->mV[1] = &v1;
 		tri->mV[2] = &v2;
 
+		//store indices
 		tri->mIndex[0] = mIndices[i];
 		tri->mIndex[1] = mIndices[i+1];
 		tri->mIndex[2] = mIndices[i+2];
 
+		//get minimum point
 		LLVector4a min = v0;
 		min.setMin(min, v1);
 		min.setMin(min, v2);
 
+		//get maximum point
 		LLVector4a max = v0;
 		max.setMax(max, v1);
 		max.setMax(max, v2);
 
+		//compute center
 		LLVector4a center;
 		center.setAdd(min, max);
 		center.mul(0.5f);
 
 		*tri->mPositionGroup = center;
 
+		//compute "radius"
 		LLVector4a size;
 		size.setSub(max,min);
 		
 		tri->mRadius = size.getLength3().getF32() * 0.5f;
 		
+		//insert
 		mOctree->insert(tri);
 	}
 
+	//calculate AABB for each node
 	LLVolumeOctreeRebound rebound(this);
 	rebound.traverse(mOctree);
+
+	if (gDebugGL)
+	{
+		LLVolumeOctreeValidate validate;
+		validate.traverse(mOctree);
+	}
 }
 
 
diff --git a/indra/llmath/llvolumeoctree.cpp b/indra/llmath/llvolumeoctree.cpp
index 194b1faf81..12fe90f35d 100644
--- a/indra/llmath/llvolumeoctree.cpp
+++ b/indra/llmath/llvolumeoctree.cpp
@@ -126,8 +126,8 @@ void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle>
 	const F32* center = vl->mBounds[0].getF32();
 	const F32* size = vl->mBounds[1].getF32();*/
 
-	//if (LLLineSegmentBoxIntersect(mStart.getF32(), mEnd.getF32(), vl->mBounds[0].getF32(), vl->mBounds[1].getF32()))
-	if (LLLineSegmentBoxIntersect(mStart, mEnd, vl->mBounds[0], vl->mBounds[1]))
+	//if (LLLineSegmentBoxIntersect(mStart, mEnd, vl->mBounds[0], vl->mBounds[1]))
+	if (LLLineSegmentBoxIntersect(mStart.getF32ptr(), mEnd.getF32ptr(), vl->mBounds[0].getF32ptr(), vl->mBounds[1].getF32ptr()))
 	{
 		node->accept(this);
 		for (S32 i = 0; i < node->getChildCount(); ++i)
@@ -206,3 +206,60 @@ const F32& LLVolumeTriangle::getBinRadius() const
 }
 
 
+//TEST CODE
+
+void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
+{
+	LLVolumeOctreeListener* node = (LLVolumeOctreeListener*) branch->getListener(0);
+
+	//make sure bounds matches extents
+	LLVector4a& min = node->mExtents[0];
+	LLVector4a& max = node->mExtents[1];
+
+	LLVector4a& center = node->mBounds[0];
+	LLVector4a& size = node->mBounds[1];
+
+	LLVector4a test_min, test_max;
+	test_min.setSub(center, size);
+	test_max.setAdd(center, size);
+
+	if (!test_min.equals3(min) ||
+		!test_max.equals3(max))
+	{
+		llerrs << "Bad bounding box data found." << llendl;
+	}
+
+	test_min.sub(LLVector4a::getEpsilon());
+	test_max.add(LLVector4a::getEpsilon());
+
+	for (U32 i = 0; i < branch->getChildCount(); ++i)
+	{
+		LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(i)->getListener(0);
+
+		//make sure all children fit inside this node
+		if (child->mExtents[0].lessThan(test_min).areAnySet(LLVector4Logical::MASK_XYZ) ||
+			child->mExtents[1].greaterThan(test_max).areAnySet(LLVector4Logical::MASK_XYZ))
+		{
+			llerrs << "Child protrudes from bounding box." << llendl;
+		}
+	}
+
+	//children fit, check data
+	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getData().begin(); 
+			iter != branch->getData().end(); ++iter)
+	{
+		const LLVolumeTriangle* tri = *iter;
+
+		//validate triangle
+		for (U32 i = 0; i < 3; i++)
+		{
+			if (tri->mV[i]->greaterThan(test_max).areAnySet(LLVector4Logical::MASK_XYZ) ||
+				tri->mV[i]->lessThan(test_min).areAnySet(LLVector4Logical::MASK_XYZ))
+			{
+				llerrs << "Triangle protrudes from node." << llendl;
+			}
+		}
+	}
+}
+
+
diff --git a/indra/llmath/llvolumeoctree.h b/indra/llmath/llvolumeoctree.h
index 0031626498..0a02a2c597 100644
--- a/indra/llmath/llvolumeoctree.h
+++ b/indra/llmath/llvolumeoctree.h
@@ -88,8 +88,6 @@ public:
 	F32* mClosestT;
 	bool mHitFace;
 
-	LLOctreeTriangleRayIntersect() { };
-
 	LLOctreeTriangleRayIntersect(const LLVector4a& start, const LLVector4a& dir, 
 								   const LLVolumeFace* face, F32* closest_t,
 								   LLVector3* intersection,LLVector2* tex_coord, LLVector3* normal, LLVector3* bi_normal);
@@ -134,5 +132,9 @@ public:
 	virtual const F32& getBinRadius() const;
 };
 
+class LLVolumeOctreeValidate : public LLOctreeTraveler<LLVolumeTriangle>
+{
+	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* branch);
+};
 
 #endif
diff --git a/indra/newview/llfloatertools.cpp b/indra/newview/llfloatertools.cpp
index fa5d9b0892..653f838779 100644
--- a/indra/newview/llfloatertools.cpp
+++ b/indra/newview/llfloatertools.cpp
@@ -1016,10 +1016,12 @@ S32 LLFloaterTools::calcRenderCost()
 		LLSelectNode *select_node = *selection_iter;
 		if (select_node)
 		{
-			LLVOVolume *viewer_volume = (LLVOVolume*)select_node->getObject();
-			if (viewer_volume)
+			LLViewerObject *vobj = select_node->getObject();
+			if (vobj->getVolume())
 			{
-				cost += viewer_volume->getRenderCost(textures);
+				LLVOVolume* volume = (LLVOVolume*) vobj;
+
+				cost += volume->getRenderCost(textures);
 				for (LLVOVolume::texture_cost_t::iterator iter = textures.begin(); iter != textures.end(); ++iter)
 				{
 					// add the cost of each individual texture in the linkset
diff --git a/indra/newview/llspatialpartition.cpp b/indra/newview/llspatialpartition.cpp
index 425fa42339..2f0641489d 100644
--- a/indra/newview/llspatialpartition.cpp
+++ b/indra/newview/llspatialpartition.cpp
@@ -3035,11 +3035,11 @@ class LLRenderOctreeRaycast : public LLOctreeTriangleRayIntersect
 {
 public:
 	
-	LLRenderOctreeRaycast(const LLVector3& start, const LLVector3& end)
+	
+	LLRenderOctreeRaycast(const LLVector4a& start, const LLVector4a& dir, F32* closest_t)
+		: LLOctreeTriangleRayIntersect(start, dir, NULL, closest_t, NULL, NULL, NULL, NULL)
 	{
-		mStart.load3(start.mV);
-		mEnd.load3(end.mV);
-		mDir.setSub(mEnd, mStart);
+
 	}
 
 	void visit(const LLOctreeNode<LLVolumeTriangle>* branch)
@@ -3050,6 +3050,17 @@ public:
 		center.set(vl->mBounds[0].getF32ptr());
 		size.set(vl->mBounds[1].getF32ptr());
 
+		if (branch->getData().empty())
+		{
+			gGL.color3f(1.f,0.2f,0.f);
+		}
+		else
+		{
+			gGL.color3f(0.75f, 1.f, 0.f);
+		}
+		
+		drawBoxOutline(center, size);
+		
 		for (U32 i = 0; i < 2; i++)
 		{
 			LLGLDepthTest depth(GL_TRUE, GL_FALSE, i == 1 ? GL_LEQUAL : GL_GREATER);
@@ -3061,9 +3072,17 @@ public:
 			else
 			{
 				gGL.color4f(0,0.5f,0.5f, 0.25f);
+				if (!branch->getData().empty())
+				{
+					drawBoxOutline(center, size);
+				}
+			}
+			
+			if (i == 1)
+			{
+				gGL.flush();
+				glLineWidth(3.f);
 			}
-
-			drawBoxOutline(center, size);
 
 			gGL.begin(LLRender::TRIANGLES);
 			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getData().begin();
@@ -3077,6 +3096,12 @@ public:
 				gGL.vertex3fv(tri->mV[2]->getF32ptr());
 			}	
 			gGL.end();
+
+			if (i == 1)
+			{
+				gGL.flush();
+				glLineWidth(1.f);
+			}
 		}
 	}
 };
@@ -3110,7 +3135,15 @@ void renderRaycast(LLDrawable* drawablep)
 				start = vobj->agentPositionToVolume(gDebugRaycastStart);
 				end = vobj->agentPositionToVolume(gDebugRaycastEnd);
 
-				LLRenderOctreeRaycast render(start, end);
+				LLVector4a starta, enda;
+				starta.load3(start.mV);
+				enda.load3(end.mV);
+				LLVector4a dir;
+				dir.setSub(enda, starta);
+
+				F32 t = 1.f;
+
+				LLRenderOctreeRaycast render(starta, dir, &t);
 				gGL.flush();
 				glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 				render.traverse(face.mOctree);