merge uv-picking branch.

svn merge -r92602:92632 svn+ssh://svn.lindenlab.com/svn/linden/branches/uv-picking-4

7 files changed, 217 insertions, 51 deletions

diff --git a/indra/llmath/llrect.h b/indra/llmath/llrect.h
index 17fa981c7c..21ca4189ff 100644
--- a/indra/llmath/llrect.h
+++ b/indra/llmath/llrect.h
@@ -183,10 +183,11 @@ public:
 
 	LLRectBase& setCenterAndSize(Type x, Type y, Type width, Type height)
 	{
+		// width and height could be odd, so favor top, right with extra pixel
 		mLeft = x - width/2;
-		mTop = y + height/2;
-		mRight = x + width/2;
 		mBottom = y - height/2;
+		mTop = mBottom + height;
+		mRight = mLeft + width;
 		return *this;
 	}
 
diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index 3b01140e3a..242b0809eb 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -104,46 +104,128 @@ BOOL check_same_clock_dir( const LLVector3& pt1, const LLVector3& pt2, const LLV
 	}
 } 
 
-// intersect test between triangle pt1,pt2,pt3 and line from linept to linept+vect
-//returns TRUE if intersecting and moves linept to the point of intersection
-BOOL LLTriangleLineSegmentIntersect( const LLVector3& pt1, const LLVector3& pt2, const LLVector3& pt3, LLVector3& linept, const LLVector3& vect)
+BOOL LLLineSegmentBoxIntersect(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& size)
 {
-	LLVector3 V1 = pt2-pt1;
-	LLVector3 V2 = pt3-pt2;
+	float fAWdU[3];
+	LLVector3 dir;
+	LLVector3 diff;
+
+	for (U32 i = 0; i < 3; i++)
+	{
+		dir.mV[i] = 0.5f * (end.mV[i] - start.mV[i]);
+		diff.mV[i] = (0.5f * (end.mV[i] + start.mV[i])) - center.mV[i];
+		fAWdU[i] = fabsf(dir.mV[i]);
+		if(fabsf(diff.mV[i])>size.mV[i] + fAWdU[i]) return false;
+	}
+
+	float f;
+	f = dir.mV[1] * diff.mV[2] - dir.mV[2] * diff.mV[1];    if(fabsf(f)>size.mV[1]*fAWdU[2] + size.mV[2]*fAWdU[1])  return false;
+	f = dir.mV[2] * diff.mV[0] - dir.mV[0] * diff.mV[2];    if(fabsf(f)>size.mV[0]*fAWdU[2] + size.mV[2]*fAWdU[0])  return false;
+	f = dir.mV[0] * diff.mV[1] - dir.mV[1] * diff.mV[0];    if(fabsf(f)>size.mV[0]*fAWdU[1] + size.mV[1]*fAWdU[0])  return false;
 	
-	LLVector3 norm = V1 % V2;
+	return true;
+}
+
+
+// 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 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 u, v, t;
+	
+	/* find vectors for two edges sharing vert0 */
+	LLVector3 edge1 = vert1 - vert0;
+	
+	LLVector3 edge2 = vert2 - vert0;;
+
+	/* begin calculating determinant - also used to calculate U parameter */
+	LLVector3 pvec = dir % edge2;
 	
-	F32 dotprod = norm * vect;
+	/* if determinant is near zero, ray lies in plane of triangle */
+	F32 det = edge1 * pvec;
 
-	if(dotprod < 0)
+	if (!two_sided)
 	{
-		//Find point of intersect to triangle plane.
-		//find t to intersect point
-		F32 t = -(norm * (linept-pt1))/dotprod;
+		if (det < F_APPROXIMATELY_ZERO)
+		{
+			return FALSE;
+		}
+
+		/* calculate distance from vert0 to ray origin */
+		LLVector3 tvec = orig - vert0;
 
-		// if ds is neg line started past triangle so can't hit triangle.
-		if (t > 0) 
+		/* calculate U parameter and test bounds */
+		u = tvec * pvec;	
+
+		if (u < 0.f || u > det)
 		{
 			return FALSE;
 		}
 	
-		LLVector3 pt_int = linept + (vect*t);
+		/* prepare to test V parameter */
+		LLVector3 qvec = tvec % edge1;
 		
-		if(check_same_clock_dir(pt1, pt2, pt_int, norm))
+		/* calculate V parameter and test bounds */
+		v = dir * qvec;
+		if (v < 0.f || u + v > det)
 		{
-			if(check_same_clock_dir(pt2, pt3, pt_int, norm))
+			return FALSE;
+		}
+
+		/* calculate t, scale parameters, ray intersects triangle */
+		t = edge2 * qvec;
+		F32 inv_det = 1.0 / det;
+		t *= inv_det;
+		u *= inv_det;
+		v *= inv_det;
+	}
+	
+	else // two sided
 			{
-				if(check_same_clock_dir(pt3, pt1, pt_int, norm))
+		if (det > -F_APPROXIMATELY_ZERO && det < F_APPROXIMATELY_ZERO)
 				{
-					// answer in pt_int is insde triangle
-					linept.setVec(pt_int);
-					return TRUE;
+			return FALSE;
 				}
+		F32 inv_det = 1.0 / det;
+
+		/* calculate distance from vert0 to ray origin */
+		LLVector3 tvec = orig - vert0;
+		
+		/* calculate U parameter and test bounds */
+		u = (tvec * pvec) * inv_det;
+		if (u < 0.f || u > 1.f)
+		{
+			return FALSE;
 			}
+
+		/* prepare to test V parameter */
+		LLVector3 qvec = tvec - edge1;
+		
+		/* calculate V parameter and test bounds */
+		v = (dir * qvec) * inv_det;
+		
+		if (v < 0.f || u + v > 1.f)
+		{
+			return FALSE;
 		}
+
+		/* calculate t, ray intersects triangle */
+		t = (edge2 * qvec) * inv_det;
 	}
 	
-	return FALSE;
+	if (intersection_a != NULL)
+		*intersection_a = u;
+	if (intersection_b != NULL)
+		*intersection_b = v;
+	if (intersection_t != NULL)
+		*intersection_t = t;
+	
+	
+	return TRUE;
 } 
 
 
@@ -3405,47 +3487,99 @@ void LLVolume::generateSilhouetteVertices(std::vector<LLVector3> &vertices,
 	}
 }
 
-S32 LLVolume::lineSegmentIntersect(const LLVector3& start, LLVector3& end) const
+S32 LLVolume::lineSegmentIntersect(const LLVector3& start, const LLVector3& end, 
+								   S32 face,
+								   LLVector3* intersection,LLVector2* tex_coord, LLVector3* normal, LLVector3* bi_normal)
 {
-	S32 ret = -1;
+	S32 hit_face = -1;
+	
+	S32 start_face;
+	S32 end_face;
 	
-	LLVector3 vec = end - start;
+	if (face == -1) // ALL_SIDES
+	{
+		start_face = 0;
+		end_face = getNumFaces() - 1;
+	}
+	else
+	{
+		start_face = face;
+		end_face = face;
+	}
+
+	LLVector3 dir = end - start;
+
+	F32 closest_t = 2.f; // must be larger than 1
 	
-	for (S32 i = 0; i < getNumFaces(); i++)
+	for (S32 i = start_face; i <= end_face; i++)
 	{
-		const LLVolumeFace& face = getVolumeFace(i);
+		LLVolumeFace face = getVolumeFace((U32)i);
+
+		LLVector3 box_center = (face.mExtents[0] + face.mExtents[1]) / 2.f;
+		LLVector3 box_size   = face.mExtents[1] - face.mExtents[0];
+
+        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);
+			}
+			
+			for (U32 tri = 0; tri < face.mIndices.size()/3; tri++) 
+			{
+				S32 index1 = face.mIndices[tri*3+0];
+				S32 index2 = face.mIndices[tri*3+1];
+				S32 index3 = face.mIndices[tri*3+2];
 
-		for (U32 j = 0; j < face.mIndices.size()/3; j++) 
+				F32 a, b, t;
+			
+				if (LLTriangleRayIntersect(face.mVertices[index1].mPosition,
+										   face.mVertices[index2].mPosition,
+										   face.mVertices[index3].mPosition,
+										   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
 		{
-			//approximate normal
-			S32 v1 = face.mIndices[j*3+0];
-			S32 v2 = face.mIndices[j*3+1];
-			S32 v3 = face.mIndices[j*3+2];
+						closest_t = t;
+						hit_face = i;
 
-			LLVector3 norm = (face.mVertices[v2].mPosition - face.mVertices[v1].mPosition) % 
-				(face.mVertices[v3].mPosition - face.mVertices[v2].mPosition);
+						if (intersection != NULL)
+						{
+							*intersection = start + dir * closest_t;
+						}
 			
-			if (norm.magVecSquared() >= 0.00000001f) 
+						if (tex_coord != NULL)
 			{
-				//get view vector
-				//LLVector3 view = (start-face.mVertices[v1].mPosition);
-				//if (view * norm < 0.0f)
+							*tex_coord = ((1.f - a - b)  * face.mVertices[index1].mTexCoord +
+										  a              * face.mVertices[index2].mTexCoord +
+										  b              * face.mVertices[index3].mTexCoord);
+
+						}
+
+						if (normal != NULL)
 				{
-					if (LLTriangleLineSegmentIntersect( face.mVertices[v1].mPosition,
-														face.mVertices[v2].mPosition,
-														face.mVertices[v3].mPosition,
-														end,
-														vec))
+							*normal    = ((1.f - a - b)  * face.mVertices[index1].mNormal + 
+										  a              * face.mVertices[index2].mNormal +
+										  b              * face.mVertices[index3].mNormal);
+						}
+
+						if (bi_normal != NULL)
 					{
-						vec = end-start;
-						ret = (S32) i;
+							*bi_normal = ((1.f - a - b)  * face.mVertices[index1].mBinormal + 
+										  a              * face.mVertices[index2].mBinormal +
+										  b              * face.mVertices[index3].mBinormal);
+						}
+
 					}
 				}
 			}
 		}		
 	}
 	
-	return ret;
+	
+	return hit_face;
 }
 
 class LLVertexIndexPair
diff --git a/indra/llmath/llvolume.h b/indra/llmath/llvolume.h
index c395ed7378..0444a02825 100644
--- a/indra/llmath/llvolume.h
+++ b/indra/llmath/llvolume.h
@@ -906,7 +906,13 @@ public:
 	//get the face index of the face that intersects with the given line segment at the point 
 	//closest to start.  Moves end to the point of intersection.  Returns -1 if no intersection.
 	//Line segment must be in volume space.
-	S32 lineSegmentIntersect(const LLVector3& start, LLVector3& end) const;
+	S32 lineSegmentIntersect(const LLVector3& start, const LLVector3& end,
+							 S32 face = -1,                          // which face to check, -1 = ALL_SIDES
+							 LLVector3* intersection = NULL,         // return the intersection point
+							 LLVector2* tex_coord = NULL,            // return the texture coordinates of the intersection point
+							 LLVector3* normal = NULL,               // return the surface normal at the intersection point
+							 LLVector3* bi_normal = NULL             // return the surface bi-normal at the intersection point
+		);
 	
 	// The following cleans up vertices and triangles,
 	// getting rid of degenerate triangles and duplicate vertices,
@@ -967,4 +973,10 @@ LLVector3 calc_binormal_from_triangle(
 		const LLVector3& pos2,
 		const LLVector2& tex2);
 
+BOOL LLLineSegmentBoxIntersect(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& 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);
+	
+	
+
 #endif
diff --git a/indra/llmath/v2math.cpp b/indra/llmath/v2math.cpp
index 7033048575..f9e62cbd53 100644
--- a/indra/llmath/v2math.cpp
+++ b/indra/llmath/v2math.cpp
@@ -33,6 +33,7 @@
 
 //#include "vmath.h"
 #include "v2math.h"
+#include "v3math.h"
 #include "v4math.h"
 #include "m4math.h"
 #include "m3math.h"
diff --git a/indra/llmath/v2math.h b/indra/llmath/v2math.h
index 5f46655a07..c896b80977 100644
--- a/indra/llmath/v2math.h
+++ b/indra/llmath/v2math.h
@@ -33,6 +33,7 @@
 #define LL_V2MATH_H
 
 #include "llmath.h"
+#include "v3math.h"
 
 class LLVector4;
 class LLMatrix3;
@@ -49,9 +50,10 @@ class LLVector2
 
 		static LLVector2 zero;
 
-		LLVector2();							// Initializes LLVector2 to (0, 0)
-		LLVector2(F32 x, F32 y);			    // Initializes LLVector2 to (x. y)
-		LLVector2(const F32 *vec);				// Initializes LLVector2 to (vec[0]. vec[1])
+		LLVector2();							  // Initializes LLVector2 to (0, 0)
+		LLVector2(F32 x, F32 y);			      // Initializes LLVector2 to (x. y)
+		LLVector2(const F32 *vec);				  // Initializes LLVector2 to (vec[0]. vec[1])
+        explicit LLVector2(const LLVector3 &vec); // Initializes LLVector2 to (vec[0]. vec[1])
 		
 		// Clears LLVector2 to (0, 0).  DEPRECATED - prefer zeroVec.
 		void	clear();
@@ -137,6 +139,12 @@ inline LLVector2::LLVector2(const F32 *vec)
 	mV[VY] = vec[VY];
 }
 
+inline LLVector2::LLVector2(const LLVector3 &vec)
+{
+	mV[VX] = vec.mV[VX];
+	mV[VY] = vec.mV[VY];
+}
+
 
 // Clear and Assignment Functions
 
diff --git a/indra/llmath/v3math.cpp b/indra/llmath/v3math.cpp
index 166761e550..12916b6253 100644
--- a/indra/llmath/v3math.cpp
+++ b/indra/llmath/v3math.cpp
@@ -34,6 +34,7 @@
 #include "v3math.h"
 
 //#include "vmath.h"
+#include "v2math.h"
 #include "v4math.h"
 #include "m4math.h"
 #include "m3math.h"
@@ -270,6 +271,13 @@ const LLVector3&	LLVector3::setVec(const LLVector4 &vec)
 	return (*this);
 }
 
+LLVector3::LLVector3(const LLVector2 &vec)
+{
+	mV[VX] = (F32)vec.mV[VX];
+	mV[VY] = (F32)vec.mV[VY];
+	mV[VZ] = 0;
+}
+
 LLVector3::LLVector3(const LLVector3d &vec)
 {
 	mV[VX] = (F32)vec.mdV[VX];
diff --git a/indra/llmath/v3math.h b/indra/llmath/v3math.h
index 051d5376b7..42ca1f88b2 100644
--- a/indra/llmath/v3math.h
+++ b/indra/llmath/v3math.h
@@ -36,6 +36,7 @@
 #include "llmath.h"
 
 #include "llsd.h"
+class LLVector2;
 class LLVector4;
 class LLMatrix3;
 class LLVector3d;
@@ -62,6 +63,7 @@ class LLVector3
 		inline LLVector3();							// Initializes LLVector3 to (0, 0, 0)
 		inline LLVector3(const F32 x, const F32 y, const F32 z);			// Initializes LLVector3 to (x. y, z)
 		inline explicit LLVector3(const F32 *vec);				// Initializes LLVector3 to (vec[0]. vec[1], vec[2])
+		explicit LLVector3(const LLVector2 &vec);				// Initializes LLVector3 to (vec[0]. vec[1], 0)
 		explicit LLVector3(const LLVector3d &vec);				// Initializes LLVector3 to (vec[0]. vec[1], vec[2])
 		explicit LLVector3(const LLVector4 &vec);				// Initializes LLVector4 to (vec[0]. vec[1], vec[2])
 		LLVector3(const LLSD& sd);