Math, geometry, and raycasting within region bounds with llCastRay.

[Wulfie Reanimator]

I recently updated a caveat on the llCastRay wiki page about region bounds, referring to this thread:

In short, if a ray crosses a region border by about 8 meters, it will start failing to detect hits even in the simplest conditions. (Like trying to hit a large default prim.)

To prevent that, we can "clamp" the ray so it always ends near a sim border, ideally in a valid location for a prim to exist. (A valid X-coordinate for an object includes 0 to 255.99999... but not 256.)

That thread already came up with a function to limit the ray within region bounds to prevent the error, but could we refine it into an example that could be included on the wiki?

Here's one example (with extra spacing for clarity), which would use the ray's starting position and direction to find a point on the nearest sim edge. The edge will be the ray's ending position.

// Use-case:
vector start = llGetPos();
vector edge = GetSimEdge(start, <1,0,0> * llGetRot());
list data = llCastRay(start, edge, []);

// The math, assuming "dir" is a unit vector:
vector GetSimEdge(vector start, vector dir)
{
    // if dir.x == 0, no value is assigned.
    vector range = <9999, 9999, 9999>;

    if      (dir.x > 0) range.x = (255.99 - start.x) /  dir.x;
    else if (dir.x < 0) range.x = (         start.x) / -dir.x;

    if      (dir.y > 0) range.y = (255.99 - start.y) /  dir.y;
    else if (dir.y < 0) range.y = (         start.y) / -dir.y;

    if      (dir.z > 0) range.z = (4095.99 - start.z) /  dir.z;
    else if (dir.z < 0) range.z = (          start.z) / -dir.z;

    // Multiply "dir" by the shortest distance/ratio: X, Y, or Z
    if      (range.x <= range.y && range.x <= range.z) return start + dir * range.x;
    else if (range.y <= range.x && range.y <= range.z) return start + dir * range.y;
    else                                               return start + dir * range.z;
}

The above calculations could be simplified a little bit to this:

vector GetSimEdge(vector start, vector dir)
{
    // Very small number to prevent divide-by-zero.
    dir += <1E-45, 1E-45, 1E-45>;

    vector range;
    range.x = ((dir.x > 0) *  255.99 - start.x) / dir.x;
    range.y = ((dir.y > 0) *  255.99 - start.y) / dir.y;
    range.z = ((dir.z > 0) * 4095.99 - start.z) / dir.z;

    if      (range.x <= range.y && range.x <= range.z) return start + dir * range.x;
    else if (range.y <= range.x && range.y <= range.z) return start + dir * range.y;
    else                                               return start + dir * range.z;
}

I'd like to ask for different or simpler solutions. Something appropriate for a wiki, without weird tricks in like the second function.

Edited November 4, 2023 by Wulfie Reanimator

[Quistess Alpha]

In the second function, I'd check the minimum after each calculation, rather than as a large check at the end, and guard with a condition rather than a small offset:

float scaleGuess;
float scaleFactor = 9999999.0; // ideally, set this such that start+dir*scaleFactor is on a region edge.
if(dir.x) // guard against zero divide.
{  scaleGuess = ((dir.x >0) *255.99-start.x)/dir.x;
   //if(scaleGuess<scaleFactor) scaleFactor = scaleGuess;
   scaleFactor = scaleGuess; // ideally, set this such that start+dir*scaleFactor is on a region edge.
}
if(dir.y)
{  scaleGuess = ((dir.y >0) *255.99-start.y)/dir.y;
   if(scaleGuess<scaleFactor) scaleFactor = scaleGuess;
}
if(dir.z)
{  scaleGuess = ((dir.z >0) *255.99-start.z)/dir.z;
   if(scaleGuess<scaleFactor) scaleFactor = scaleGuess;
}

return start+dir*scaleFactor;

but I don't think there's much else you can do unless you settle for approximating the region-boundary-cube with a 'nicer' function.

[Quistess Alpha]

another 'solution' would be to pull the ending point inside the region without taking the start point into account (untested):

vector pull_to_region(vector point)
{   vector diff = point-<128,128,128>;
    float scale = 1.0;
    float f; // temp variable
    if((f=llFabs(diff.x))>127.99)
    {   scale = 127.99/f;
    }
    if((f=llFabs(diff.y))>127.99)
    {   f = 127.99/f;
        if(f<scale) scale=f;
    }
    if((f=llFabs(diff.z))>127.99)
    {   f = 127.99/f;
        if(f<scale) scale=f;
    }
    return (scale*diff)+<128,128,128>;
}

but that seems almost as complicated.

another bad solution, would be to guess and check distances from the start point: decrement dist starting from 360 (distance from one corner to another) until start+dir*dist is inside the region.

// roughly:
vector GetSimEdge(vector start, vector dir) // WARNING: may infinite loop if start is outside region!
{   float dist = 360.0;
    vector edge;
    do
    {   edge = start+dir*dist;
        dist -= 10.0;
    }while(edge.x<0 && edge.x>=256.0 && edge.y<0 && edge.y >=256.0 && edge.z<0 && edge.z>256.0 )
    return edge;
}

 

Edited November 4, 2023 by Quistess Alpha

[Wulfie Reanimator]

6 hours ago, Quistess Alpha said:

I don't think there's much else you can do unless you settle for approximating the region-boundary-cube with a 'nicer' function.

I'd be all for it, I've been racking my brain while looking at the usual (Sutherland, Cyrus, Barsky, Nicholl) clipping algorithms. All I can come up with are either really long functions or short but very "dense" functions.

I want to imagine there's something to be gained from the assumption that one point will always be within the region. It's very hard to find anything to corroborate that though.

Or maybe I'm just overthinking the whole thing. 🙂 That's why I'm asking here.

[elleevelyn]

15 hours ago, Quistess Alpha said:

In the second function, I'd check the minimum after each calculation

i would go with this method

i think that this Quistess method is the most efficient in the sense that it only does the math as/when required rather than do all the math then pick out what is needed

also for wiki purposes, this kind of function is quite advanced as is the whole topic of ray casting which is not really a beginner scripter task. Is more a mid-level plus task. And as such I think these kinds of functions should be more directed toward the mid-level. To be fair also, beginner level scripters will typically just cut n' paste wiki code snippets into their scripts, so knowing this is I think is better to  go with the more efficient method, even when the code (inline math) can sometimes be a bit murky for a beginner

tidying it up a tiny bit and I am not sure that it can be done more efficiently, and to another point I think this method is quite elegant compared to the other offerings

vector GetSimEdge(vector start, vector dir)
{
    float scaleGuess;
    float scaleFactor = 4095.99;
    if (dir.x)
    {  
        scaleFactor = ((dir.x > 0) * 255.99 -start.x) / dir.x;
    }
    if (dir.y)
    {  
        scaleGuess = ((dir.y > 0) * 255.99 - start.y) / dir.y;
        if (scaleGuess < scaleFactor) scaleFactor = scaleGuess;
    }
    if (dir.z)
    {  
        scaleGuess = ((dir.z > 0) * 4095.99 - start.z) / dir.z;
        if (scaleGuess < scaleFactor) scaleFactor = scaleGuess;
    }
    return start + dir * scaleFactor;
}

 

 

 

[Wulfie Reanimator]

5 hours ago, elleevelyn said:

i think that this Quistess method is the most efficient in the sense that it only does the math as/when required rather than do all the math then pick out what is needed

That definitely seems to be the case! Using the performance test script from the wiki, Quistess' version (from your post) is about 50% faster than my first example. Sometimes a little more, sometimes a little less, but the difference is significant.

I also agree that the raycasting functions are at least intermediate stuff, but I would still feel bad if I added some obscure code to the page (referring to my second example... which is slower than the original).

Edit: The examples for llCastRay have been updated with a simple example and the GetSimEdge function.

Edited November 5, 2023 by Wulfie Reanimator