diff options
author | Karl Steifvater <qarl@lindenlab.com> | 2008-07-23 21:20:19 +0000 |
---|---|---|
committer | Karl Steifvater <qarl@lindenlab.com> | 2008-07-23 21:20:19 +0000 |
commit | 52562e2e664c70dcd476291820ac02b893e489b8 (patch) | |
tree | 5137f49f194a6a28f290385c38f689d77656b2e0 /indra/llmath | |
parent | bc39ad916e8f23ffae12184eee675aa7c1be2ca9 (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.h | 5 | ||||
-rw-r--r-- | indra/llmath/llvolume.cpp | 224 | ||||
-rw-r--r-- | indra/llmath/llvolume.h | 14 | ||||
-rw-r--r-- | indra/llmath/v2math.cpp | 1 | ||||
-rw-r--r-- | indra/llmath/v2math.h | 14 | ||||
-rw-r--r-- | indra/llmath/v3math.cpp | 8 | ||||
-rw-r--r-- | indra/llmath/v3math.h | 2 |
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); |