Little bit of math/geometry help...

I'll try to explain this in a simple way...

I have an object with velocity ObjectVel (Vector of course) as well as its position ObjectPos.


Then I have an avatar at position AvPos, now I need to calculate if the object will collide with the avatar, I'm basically looking for a simple way to determine if the object will cross over AvPos +- <0.5,0.5,1>.


Any help would be appreciated, I can be contacted in game as well, I should be on for a while, happy to share what I'm working on.

A ray tracing problem! Woo hoo! Okay. You're asking whether a ray intersects an ellipsoid. The equation for a line is:

u = p + t*v

where p is any point on the line, t is any real scalar and v is a (normal) vector in the direction of the line. The equation for an ellipsoid (with its major axes aligned to x, y, and z) is:

u.x^2/a^2 + u.y^2/b^2 + u.z^2/c^2 = 1

where a, b, and c are the lenghs of the ellipsoid's radii (in your case, 0.5, 0.5, and 1.0). After a bit of substitution and such, this becomes:

(v.x^2/a^2 + v.y^2/b^2+v.z^2/c^2)*t^2
+ 2*(p.x*v.x/a^2 + p.y*v.y/b^2 + p.z*v.z/c^2)*t
+ (p.x^2/a^2 + p.y^2/b^2 + p.z^2/c^2) = 1

...which can be solved (both for the existence of a solution and the distance t along the line) using the quadratic equation. Skipping to some code:

// Returns the distances along a line where a line intersects an (axis-aligned)
// ellipsoid.  If the line doesn't intersect, the list will be empty.  If the
// line just barely skims the surface, it will have one length.  If the line
// passes through the center, it will have two lengths.  The lengths are sorted
// from least to greatest.
// param rayPoint - The beginning of the ray.
// param rayDir - A normal vector pointing in the direction of the ray's line.
// param ellipsoidCenter - The center point of the ellipsoid.
// param ellipsoidXRadius - The radius of the ellipsoid along the x-axis
// param ellipsoidYRadius - The radius of the ellipsoid along the y-axis
// param ellipsoidZRadius - The radius of the ellipsoid along the z-axis
// returns - A list of lenths along the line/ray, sorted from least to greatest.
//           For length 'L', the point of intersection may be calculated as
//           'rayPoint+L*rayDir'.
integer rayEllipsoidIntersectionDistances(
   vector rayPoint, vector rayDir,
   vector ellipsoidCenter,
   float ellipsoidXRadius, float ellipsoidYRadius, float ellipsoidZRadius)
{
   float aSq = ellipsoidXRadius*ellipsoidXRadius;
   float bSq = ellipsoidYRadius*ellipsoidYRadius;
   float cSq = ellipsoidZRadius*ellipsoidZRadius;

   // Note that c2 is always positive
   float c2 =
      rayDir.x*rayDir.x/aSq
      +rayDir.y*rayDir*y/bSq
      +rayDir.z*rayDir.z/cSq;
   float c1 =
      2.0*(rayPoint.x*rayDir.x/aSq
           +rayPoint.y*rayDir*y/bSq
           +rayPoint.z*rayDir.z/cSq);
   float c0 =
      rayPoint.x*rayPoint.x/aSq
      +rayPoint.y*rayPoint.y/bSq
      +rayPoint.z*rayPoint.z/cSq
      -1.0;

   float discriminant = c1^2-4.0*c2*c0;
   if (discriminant < 0.0)
   {
      return [];
   } else if (discriminant < 0.0000001)
   {
      return [ -0.5*c1/c2 ];
   } else
   {
      float m = 0.5/c2;
      float sqrt = llSqrt(discriminant);
      return [ m*(-c1-sqrt), m*(-c1+sqrt) ];
   }
}

Now if any positive length is returned from 'rayEllipsoidIntersectionDistances(ObjectPos, llVecNorm(ObjectVel), AvPos, 0.5, 0.5, 1.0)' then your object would collide.

NOTE: This assumes your object is very small. If it is anywhere approaching the scale of 0.5m, you might want to approximate it as a sphere and add its radius to each of the radii of your ellipsoid.

Okay. That was also for an ellipsoid, which may not be ALL that accurate. But it did sound like you wanted an approximate answer. It could also be done for a cylinder or (a bit more ugly) a rectangular prism. I think in Havok 4 avatars are cylinders. Maybe I'll do that one too and post it in a bit.

Can't this be done with a little vector subtraction and a bit of llVecNorm'ing?

For a cylinder this is a little simpler, but more work has to be done outside the raycasting.

// Returns the distances along a line where a line intersects a (z-axis aligned)
// cylinder.  If the line doesn't intersect, the list will be empty.  If the
// line just barely skims the surface, it will have one length.  If the line
// passes through the center, it will have two lengths.  The lengths are sorted
// from least to greatest.
// param rayPoint - The beginning of the ray.
// param rayDir - A normal vector pointing in the direction of the ray's line.
// param cylinderCenter - The a point on the axis of the cylinder.
// param cylinderRadius - The radius of the cylinder along the x-and y-axes
// returns - A list of lenths along the line/ray, sorted from least to greatest.
//           For length 'L', the point of intersection may be calculated as
//           'rayPoint+L*rayDir'.
integer rayCylinderIntersectionDistances(
   vector rayPoint, vector rayDir,
   vector cylinderCenter, float cylinderRadius)
{
   // Convenience.  Allows us to use vector dot product while ignoring z.
   rayPoint.z = 0.0;
   rayDir.z = 0.0;

   // Note that c2 is always positive
   float c2 = rayDir*rayDir;
   float c1 = 2.0*rayDir*rayPoint;
   float c0 = rayPoint*rayPoint-cylinderRadius*cylinderRadius;

   float discriminant = c1^2-4.0*c2*c0;
   if (discriminant < 0.0)
   {
      return [];
   } else if (discriminant < 0.0000001)
   {
      return [ -0.5*c1/c2 ];
   } else
   {
      float m = 0.5/c2;
      float sqrt = llSqrt(discriminant);
      return [ m*(-c1-sqrt), m*(-c1+sqrt) ];
   }
}

Now find the points of intersection (if any) and compare their heights to the height of your avatar to see if they are more or less than 1m different.

Hmm, thanks for the help, figured out a much simpler solution by dividing the distance by the velocity and comparing the position after that much time had passed =)

oh you little!

I for one enjoyed the raytracing but i fear that all the llPow(x,2) will be slow and inaccurate on floats.

Probably accurate enough, especially given the required accuracy. Slow possibly. I did optimize those as much as possible. Definitely compile to MONO!