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

3 files changed, 100 insertions, 28 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