summaryrefslogtreecommitdiff
path: root/indra/llmath
diff options
context:
space:
mode:
authorKarl Steifvater <qarl@lindenlab.com>2008-07-23 21:20:19 +0000
committerKarl Steifvater <qarl@lindenlab.com>2008-07-23 21:20:19 +0000
commit52562e2e664c70dcd476291820ac02b893e489b8 (patch)
tree5137f49f194a6a28f290385c38f689d77656b2e0 /indra/llmath
parentbc39ad916e8f23ffae12184eee675aa7c1be2ca9 (diff)
svn merge -r92720:92721 svn+ssh://svn.lindenlab.com/svn/linden/branches/uv-picking-merge
QAR-698 / DEV-9985 add touch "position" information to touch-events in LSL
Diffstat (limited to 'indra/llmath')
-rw-r--r--indra/llmath/llrect.h5
-rw-r--r--indra/llmath/llvolume.cpp224
-rw-r--r--indra/llmath/llvolume.h14
-rw-r--r--indra/llmath/v2math.cpp1
-rw-r--r--indra/llmath/v2math.h14
-rw-r--r--indra/llmath/v3math.cpp8
-rw-r--r--indra/llmath/v3math.h2
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);