Help optimizing a function

I have this function I have made to determine whether a physical object is on a path intersecting me, however, it is much too slow for the speed i need it to operate at; it comes up at 0.1 to 0.15 sec per calculation. I need it to be fast enough the calculating object can actually move to avoid the incoming object, before the incoming object impacts it. Thus I am gonna post it here in the hopes someone more brilliant than I can tinker with it, possibly improving the speed. =P

integer checktraj(integer num)
{
//llResetTime();
list bb = llGetBoundingBox(llDetectedKey(num));
vector scale = -llList2Vector(bb, 0) + llList2Vector(bb, 1);
float gm = (scale.x + scale.y + scale.z) / 3.0;
vector tp = llDetectedPos(num);
vector mp = llGetPos();
float dist = llVecDist(mp,tp);
float rr = llVecMag((tp + (llVecNorm(llDetectedVel(num)) * dist)) - mp);
if(rr <= gm)return TRUE;
else return FALSE;
//return (string)rr + " "+(string)llGetTime();
}

I don't want to tinker, but let me offer two suggestions:

1. Anything having to do with lists is slow, and probably the bounding function is slow. Replace that section with your own code.

2. llVecDist and llVecMag both take costly square roots, and 2<=3 iff 4<=9. Calculate the squares of those two quantities with an explicit formula and compare them.

You have two vectors, and you want to see if they intersect...right?

I bet there is some clever vector test to do this? Engineers? Physicists? Speak out.

(1) It is probably difficult to compute for sure if the two objects will touch each other. But I assume that it is at least a good start if you can find a procedure that might give you some false positives (tells you that they might hit each other, even if they won't), but no false negatives (if it tells you they won't hit each other, you know that you are safe).

So I suggest that first you consider balls that contain the two objects, and see if they intersect. The distance you use , gm = (scale.x+scale.y+scale.z)/3, is not big enough to make sure that a ball of this radius contains the bounding box - what if scale = <10,1,1>? But if we use radius d^2 = D = (scale.x^2+scale.y^2+scale.z^2)/4 so that d=llVecMag(scale)/2, then d will do. Possibly, this can be cleverly improved.

(2) You should also take into account that the object the scipt is in also has a certain size. So lets assume that the objects with the script has position a, the other llDetectedPos() = b, the radius of balls containing them are d1 and d2, where d1^2=D1 and d2^2=D2 as before. Put u = a-b; Also assume that the object the script is in does not move (if it does move, it is easy to compensate for that), and the other object has velocity

vector v = llDetectedVel();

Further:

float d = d1+ d2;
float r = u*u;
float s = u*v;
float t = v* v:

By vector algebra, the two obejcts will not collide if

r * t > s * s + d ^2 * t

(3) If this can be done in less than 0.1 seconds I don't know..

This is approximate, but it is fast.

given an actor, A, with vel, pos, and radius.
given a bullet, B, with vel, pos, and radius.
give a time T to extrapolate into the future.

Q: Will bullet hit A (enter its radius) within time T?

Let

r = radius of A + radius of B.
v = velocity of B - velocity of A
p = position of B - position of A

now, look at two points. P0 = p is where the bullet is now. P1 = p + vT is where the bullet will be after T (if it goes straight).

If llVecMag(P0) > r AND llVecMag(P1) > r
then B probably misses A.

This test fails for some cases, such as the bullet passes all the way through the A radius during time T.

But this sound unlkely to matter in your case. Making T smaller would help. You could also add a test for llVecMag( (P0+P1)/2 ).

Let me know if this works.

How about a simplistic check like this. I just threw it down but the gist is to project its movement forward as you have, but simply check a rough boundary of its path vs a cube of roughly your size?

list bbMe;
float myRad;
vector tp;
vector mp;
float dist;
vector do;

func()
{
bbMe = []+llGetBoundingBox(llGetOwner());
myRad = (llList2Vector(bbMe, 1).z - llList2Vector(bbMe, 0).z) / 2;
tp = llDetectedPos(num);
mp = llGetPos();
dist = llVecDist(mp,tp);
do = tp + (llVecNorm(llDetectedVel(num)) * dist;

if( (llFabs(do.x-mp.x)>myRad) && (llFabs(do.y-mp.y)>myRad) && (llFabs(do.z-mp.z)>myRad))
return TRUE;
else
return FALSE
}

Brainstorm on the way home.

Let

r = radius of A + radius of B.
v = velocity of B - velocity of A
p = position of B - position of A
T = time ahead to forecast

Now, look at two points. P0 = p is where the bullet is now. P1 = p + vT is where the bullet will be after T (if it goes straight).

Let d0 = llVecMag(P0)

d0 is large --> B probably is far enough way that we don't need to evade yet. return
d0 < r -> we are about to be hit, or at least suffer a near miss. return

if we didn't return yet, then let d1 = llVecMag(P1)
d1 > d0 --> B is going away from us. relax. return
d1 < r --> yikes! we are about to be hit.



Another idea is to look at The vector Po and P1, and the distances d0 and d1.

If
d1 < d0 && the angle between P0 and P1 is small,
then
B is coming at A. if d1 is near r, evade
else
B is going away from A. relax.

Shadows idea and mine are very similar. He uses bounding boxes, while I use a sphere. His will probably not evade as much, but will have the over head of the List2Vector stuff.

Actually mine should calculate the 1/2 width (radius) for each axis separately. When I started typing, I was thinking sphere, hence the one radius. I would submit this to be a bit more accurate. Also keep in mind that this does not account for the size of the object, it is purely checking whether its path might collide. Its width could be added in by getting its bounding box similar to the original posted code. I guess its a question of where you want to make compromises to reduce overhead.

//bounding box on me
list bbMe;
//bounding box corners
vector maxPoint;
vector minPoint;

//1/2 width of me on each axis
float myRadx;
float myRady;
float myRadz;

//position of object targetting me
vector tp;

//position of me
vector mp;

//distance between object and me
float dist;

//position of object after projection forward on its path
vector do;

func()
{
bbMe = []+llGetBoundingBox(llGetOwner());

maxPoint = llList2Vector(bbMe, 1);
minPoint = llList2Vector(bbMe, 0);

myRadx = maxPoint.x-minPoint.x/2;
myRady = maxPoint.y-minPoint.y/2;
myRadz = maxPoint.z-minPoint.z/2;

tp = llDetectedPos(num);
mp = llGetPos();
dist = llVecDist(mp,tp);
do = tp + (llVecNorm(llDetectedVel(num)) * dist;

if( (llFabs(do.x-mp.x)<myRadx) && (llFabs(do.y-mp.y)<myRady) && (llFabs(do.z-mp.z)<myRadz))
return TRUE;
else
return FALSE
}